什么是Java优先级队列？

2019-12-17 16:02:32来源：博客园阅读 ()

什么是Java优先级队列？

PriorityQueue是基于无界优先级队列和优先级堆构建的重要Java API之一。本文通过适当的代码示例深入了解了有关此API及其用法的一些复杂信息。另在上篇文章中我们简单地谈了下Java编译器API简介，你可以先阅读以方便更好地阅读这篇文章。感谢优锐课老师对我写下这两篇文章时给予的帮助。

总览

PriorityQueue类是java.util包的一部分，是Java中基于优先级的队列的通用实现。队列基本上是一种数据结构，它定义了针对商店中商品的插入和检索过程的特定规范。这个想法与排队等候说票的许多人非常相似。排队的第一个人有第一个获得彩票的机会，最后一个人有一个结局的机会。人们被添加到队列的末尾或末尾。在队列中添加项目在技术上称为入队过程，从队列中删除的项目是从该行的第一行开始。这称为出队。想法是以先进先出的方式对元素进行排序。

现在，这是最简单的体系结构，并且紧密定义了队列的实际含义以及如何在计算机中模拟队列。存储通常由一个简单的数组表示，其中存储和检索过程具有此定义的规范。优先级队列在此之上强加一些特殊规范。我们将在后面看到更多内容。

队列的Java实现

Java API在java.util包中具有通用接口名称Queue <E>。这是Java Collection Framework API的一部分，旨在在处理之前保存元素。作为集合的一部分，它具有所有基本的集合操作。特定于其标识的操作涉及存储在其中的元素的插入，提取和检查。这些操作中的每一个都有两种不同的形式，例如一种在操作失败时引发异常，而另一种则根据操作返回一个特殊值，例如null或false。请注意，与典型队列不同，Java Queue的具体实现不必一定以FIFO方式对元素进行排序。对于基于优先级的队列尤其如此，其中元素的排序是根据提供的比较器或自然排序完成的。但是无论顺序如何，remove（）或poll（）方法将始终检索队列开头的元素。这两种不太可能的方法之间的特定区别似乎是一种相似的方法，即在失败时引发异常（NoSuchElementException），而后者则返回特殊值（null）。

方法	引发异常			描述
E remove()	NoSuchElementException			从队列的开头检索一个元素。
void add(E)	IllegalStateException			在队列末尾插入一个元素。成功返回true，如果空间不可用则抛出异常。
E element()	NoSuchElementException			检索元素而不将其从队列的开头移除。

方法		返回特殊值	说明
boolean offer(E)		true or false	将元素插入队列。成功返回true，如果由于空间不足而无法插入，则返回false。
E poll()		null	从队列的开头移除元素；如果队列为空，则返回null。
E peek()		null	检索但不从队列的开头删除元素。如果队列为空，则返回null。

请注意，Queue <E>接口不适用于并发编程，因为它没有定义阻塞队列方法，在这种方法中，入队和出队过程等待元素出现在队列中或大小可用。有一个名为BlockingQueue <E>的特定接口，该接口扩展了Queue <E>接口并解决了这些问题。

有一个称为AbstractQueue <E>的抽象类，该类提供某些队列操作的部分实现。 PriorityQueue <E>类是此抽象类的直接扩展。

优先队列

优先级队列的Java实现是一种特殊的队列，其中元素的排序由其自然排序原则确定，也可以根据创建期间提供的Comparator进行定制。我们在构造过程中调用的构造函数决定要与优先级队列一起使用的排序原则。与不允许使用null元素的Queue <E>不同，但是某些实现（例如LinkedList）也不禁止插入null元素。但是，PriorityQueue <E>根本不允许空元素。如果优先级队列是根据自然顺序构造的，则任何不可比较的元素插入都将引发ClassCastException。

它被声明为无限制的并且基于优先级堆。尽管队列的大小被称为无限制，但内部具有确定阵列大小的能力。插入元素时，此大小会自动增长。但是，没有详细说明增大尺寸的原理。

有七种类型的重载构造函数，通过它们我们可以设置参数来指定队列的初始容量，提供Comparator来指定元素的自定义顺序，或者使用无参数构造函数将所有内容接受为默认值。

PriorityQueue()
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity, Comparator<? Super E> comparator)
PriorityQueue(Commection<? extends E> c)
PriorityQueue(Comparator<? Super E> comparator)
PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)

与Queue <E>相似，PriorityQueue <E>也不同步，因此在并发编程中应谨慎使用。但是，有一个同步的替代方法，称为PriorityBlockingQueue <E>。这与PriorityQueue <E>的工作方式相同，只是具有线程安全的其他限定条件。

PriorityQueue <E>中定义的操作与Queue <E>相同，但有一些附加功能。

方法	描述
void clear()	从优先级队列中删除所有元素。
Comparator<? Super E> comparator()	返回与队列关联的比较器。如果根据自然顺序对队列进行排序，则返回null。
boolean contains(Object o)	如果队列包含指定的对象，则返回true。
Iterator<E> iterator()	返回与Collection类关联的旧式迭代器。但是，它不能保证以任何特定顺序遍历元素。
Spliterator<E> spliterator()	创建后期绑定，故障快速拆分器，但具有与迭代器相同的条件。
Object[] toArray()	这是一种便捷方法，可用于设置遍历顺序权限，例如`Arrays.sort(priorityQueue.toArray())`.
<T>T[] toArray(T[] a)	返回数组元素，但是返回类型由指定的数组确定。

快速示例1

让我们用一个简单的程序实现PriorityQueue <E>的一些操作。

 1 package org.mano.examples;
 2 import java.util.Arrays;
 3 import java.util.Iterator;
 4 import java.util.PriorityQueue;
 5 public class Example1 {
 6    public static void main(String[] args){
 7       PriorityQueue<String> pq = new PriorityQueue<>();
 8       pq.add("Mercury");
 9       pq.add("Venus");
10       pq.add("Earth");
11       pq.add("Mars");
12       pq.add("Jupiter");
13       pq.add("Saturn");
14       // Get the most priority element based upon
15       // natural alphabetic ordering in string
16       System.out.println("Priority element "+pq.peek());
17       // Queue elements
18       show(pq);
19       // Remove top of the queue element
20       pq.poll();
21       show(pq);
22       // Retrieves element from the head of the queue
23       pq.remove("Earth");
24       show(pq);
25       String result = pq.contains("Earth")?
26          "Found Earth":"Earth Missing!";
27       System.out.println(result);
28       Object[] arr = pq.toArray();
29       Arrays.sort(arr);
30       System.out.println("");
31       for (int i = 0; i<arr.length; i++)
32          System.out.print(arr[i].toString()+"::");
33    }
34    public static void show(PriorityQueue<String> pq){
35       Iterator<String> itr = pq.iterator();
36       while (itr.hasNext())
37          System.out.print(itr.next()+"::");
38          System.out.println("");
39    }
40 }

Output

1 Priority element Earth
2 Earth::Jupiter::Mercury::Venus::Mars::Saturn::
3 Jupiter::Mars::Mercury::Venus::Saturn::
4 Jupiter::Mars::Mercury::Venus::Saturn::
5 Earth Missing!
6  
7 Jupiter::Mars::Mercury::Saturn::Venus::

快速示例2

这是另一个带有自定义比较器的快速示例。

 1 package org.mano.examples;
 2 import java.util.Comparator;
 3 import java.util.PriorityQueue;
 4 public class Planet implements Comparable<Planet>{
 5    private String name;
 6    private double orbitPeriodInDays;
 7    public Planet(String name, double orbitPeriodInDays) {
 8       this.name = name;
 9       this.orbitPeriodInDays = orbitPeriodInDays;
10    }
11    public String getName() {
12       return name;
13    }
14    public void setName(String name) {
15       this.name = name;
16    }
17    public double getOrbitPeriodInDays() {
18       return orbitPeriodInDays;
19    }
20    public void setOrbitPeriodInDays(double orbitPeriodInDays) {
21       this.orbitPeriodInDays = orbitPeriodInDays;
22    }
23    @Override
24    public int compareTo(Planet o) {
25       return 0;
26    }
27    @Override
28    public String toString() {
29       return "Planet{" +
30          "name='" + name + '\'' +
31          ", orbitPeriodInDays=" + orbitPeriodInDays +
32          '}';
33    }
34    public static void main(String[] args){
35       Comparator<Planet> nameSorter =
36          Comparator.comparing(Planet::getName);
37       PriorityQueue<Planet> priorityQueue = new
38          PriorityQueue<>(nameSorter);
39       priorityQueue.add(new Planet("Mercury",88));
40       priorityQueue.add(new Planet("Venus",225));
41       priorityQueue.add(new Planet("Earth",365.24));
42       priorityQueue.add(new Planet("Mars",693.5));
43       priorityQueue.add(new Planet("Jupiter",4343.5));
44       priorityQueue.add(new Planet("Saturn",10767.5));
45       priorityQueue.add(new Planet("Uranus",30660));
46       priorityQueue.add(new Planet("Neptune",60152));
47       Object[] list = priorityQueue.toArray();
48       for (Object o: list)
49          System.out.println(o);
50    }
51 }

Output

1 Planet{name='Earth', orbitPeriodInDays=365.24}
2 Planet{name='Jupiter', orbitPeriodInDays=4343.5}
3 Planet{name='Mercury', orbitPeriodInDays=88.0}
4 Planet{name='Neptune', orbitPeriodInDays=60152.0}
5 Planet{name='Mars', orbitPeriodInDays=693.5}
6 Planet{name='Saturn', orbitPeriodInDays=10767.5}
7 Planet{name='Uranus', orbitPeriodInDays=30660.0}
8 Planet{name='Venus', orbitPeriodInDays=225.0}