Question

java.lang.Object
  └java.util.AbstractCollection<E>
      └java.util.AbstractQueue<E>
          └java.util.PriorityQueue<E>

类型参数：

E - 集合中所保存元素的类型。

所有已实现的接口：

Serializable, Iterable<E>, Collection<E>, Queue<E>

---

public class PriorityQueue<E>

extends AbstractQueue<E>

implements Serializable

一个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序，既可以根据元素的自然顺序 来指定排序（参阅 Comparable ），也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException ）。

此队列的头 是按指定排序方式的最小 元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列检索操作 poll 、 remove 、 peek 和 element 访问处于队列头的元素。

优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组的大小。它总是至少与队列的大小相同。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。

此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。方法 iterator() 中提供的迭代器并不 保证以任意特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray()) 。

注意，此实现不是同步的。如果多个线程中的任意线程从结构上修改了列表，则这些线程不应同时访问 PriorityQueue 实例。相反，请使用线程安全的 PriorityBlockingQueue 类。

实现注意事项：此实现为插入方法（ offer 、 poll 、 remove() 和 add 方法）提供 O(log(n)) 时间；为 remove(Object) 和 contains(Object) 方法提供线性时间；为检索方法（ peek 、 element 和 size ）提供固定时间。

此类是 Java Collections Framework 的成员。

从以下版本开始：

1.5

另请参见：

序列化表格

---

构造方法摘要
PriorityQueue() 使用默认的初始容量（11）创建一个 PriorityQueue ，并根据其自然顺序来排序其元素（使用 Comparable ）。
PriorityQueue(Collection<? extends E>c) 创建包含指定集合中元素的 PriorityQueue 。
PriorityQueue(intinitialCapacity) 使用指定的初始容量创建一个 PriorityQueue ，并根据其自然顺序来排序其元素（使用 Comparable ）。
PriorityQueue(intinitialCapacity, Comparator<? super E>comparator) 使用指定的初始容量创建一个 PriorityQueue ，并根据指定的比较器来排序其元素。
PriorityQueue(PriorityQueue<? extends E>c) 创建包含指定集合中元素的 PriorityQueue 。
PriorityQueue(SortedSet<? extends E>c) 创建包含指定集合中元素的 PriorityQueue 。

方法摘要
boolean	add(Eo) 向队列中添加指定的元素。
void	clear() 从优先级队列中移除所有元素。
Comparator<? super E>	comparator() 返回用于排序集合的比较器，或者如果此集合根据其元素的自然顺序排序（使用 Comparable ），则返回 null 。
Iterator<E>	iterator() 返回在队列中的元素上进行迭代的迭代器。
boolean	offer(Eo) 向优先级队列中插入指定的元素。
E	peek() 检索，但是不移除此队列的头，如果此队列为空，则返回 null 。
E	poll() 检索并移除此队列的头，如果此队列为空，则返回 null 。
boolean	remove(Objecto) 从队列中移除指定元素的单个实例（如果其存在）。
int	size() 返回此 collection 中的元素数。

从类 java.util.AbstractQueue 继承的方法
addAll, element, remove

从类 java.util.AbstractCollection 继承的方法
contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

从类 java.lang.Object 继承的方法
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

从接口 java.util.Collection 继承的方法
contains, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

构造方法详细信息

PriorityQueue

public PriorityQueue()

使用默认的初始容量（11）创建一个 PriorityQueue ，并根据其自然顺序来排序其元素（使用 Comparable ）。

---

PriorityQueue

public PriorityQueue(intinitialCapacity)

使用指定的初始容量创建一个 PriorityQueue ，并根据其自然顺序来排序其元素（使用 Comparable ）。

参数：

initialCapacity - 优先级队列的初始容量。

抛出：

IllegalArgumentException - 如果 initialCapacity 小于 1。

---

PriorityQueue

public PriorityQueue(intinitialCapacity,
                     Comparator<? super E>comparator)

使用指定的初始容量创建一个 PriorityQueue ，并根据指定的比较器来排序其元素。

参数：

initialCapacity - 优先级队列的初始容量。

comparator - 用于排序优先级队列的比较器。如果为 null ，则顺序取决于元素的自然顺序。

抛出：

IllegalArgumentException - 如果 initialCapacity 小于 1。

---

PriorityQueue

public PriorityQueue(Collection<? extends E>c)

创建包含指定集合中元素的 PriorityQueue 。该优先级队列的初始容量是指定集合大小的 110％，或者如果集合是空的，则为 1。如果指定的集合是 SortedSet 的一个实例或者是另一个 PriorityQueue ，那么优先级队列将根据相同的比较器进行排序，或者如果集合是根据其元素的自然顺序排序的，则该队列也根据元素的自然顺序进行排序。否则优先级队列根据其元素的自然顺序排序。

参数：

c - 集合，其元素要置于此优先级队列中。

抛出：

ClassCastException - 如果根据优先级队列的排序规则无法比较指定集合中的各个元素。

NullPointerException - 如果 c 或其中的任意元素为 null 。

---

PriorityQueue

public PriorityQueue(PriorityQueue<? extends E>c)

创建包含指定集合中元素的 PriorityQueue 。该优先级队列的初始容量是指定集合大小的 110％，或者如果集合是空的，则为 1。优先级队列将根据与给定集合相同的比较器进行排序，或者如果集合是根据其元素的自然顺序排序的，则该队列也根据其元素的自然顺序进行排序。

参数：

c - 集合，其元素要置于此优先级队列中。

抛出：

ClassCastException - 如果根据优先级队列的排序规则无法比较指定集合中的各个元素。

NullPointerException - 如果 c 或其中的任意元素为 null 。

---

PriorityQueue

public PriorityQueue(SortedSet<? extends E>c)

创建包含指定集合中元素的 PriorityQueue 。该优先级队列的初始容量是指定集合大小的 110％，或者如果集合是空的，则为 1。优先级队列将根据与给定集合相同的比较器进行排序，或者如果集合是根据其元素的自然顺序排序的，则该队列也根据其元素的自然顺序进行排序。

参数：

c - 集合，其元素要置于此优先级队列中。

抛出：

ClassCastException - 如果根据优先级队列的排序规则无法比较指定集合中各个元素。

NullPointerException - 如果 c 或其中的任意元素为 null 。

方法详细信息

offer

public boolean offer(Eo)

向优先级队列中插入指定的元素。

指定者：

接口 Queue<E> 中的 offer

参数：

o - 要插入的元素。

返回：

true

抛出：

ClassCastException - 如果根据优先级队列的排序规则无法将指定的元素与当前优先级队列中存在的元素进行比较。

NullPointerException - 如果指定的元素为 null 。

---

peek

public E peek()

从接口 Queue 复制的描述

检索，但是不移除此队列的头，如果此队列为空，则返回 null 。

指定者：

接口 Queue<E> 中的 peek

返回：

队列的头，或者如果此队列为空，则返回 null 。

---

add

public boolean add(Eo)

向队列中添加指定的元素。

指定者：

接口 Collection<E> 中的 add

覆盖：

类 AbstractQueue<E> 中的 add

参数：

o - 元素

返回：

true （按照 Collection.add 的通用协定）。

抛出：

NullPointerException - 如果指定的元素为 null 。

ClassCastException - 如果根据优先级队列的排序规则无法将指定的元素与当前优先级队列中存在的元素进行比较。

---

remove

public boolean remove(Objecto)

从队列中移除指定元素的单个实例（如果其存在）。

指定者：

接口 Collection<E> 中的 remove

覆盖：

类 AbstractCollection<E> 中的 remove

参数：

o - 要从此 collection 中移除的元素（如果存在）。

返回：

如果该 collection 包含指定的元素,则返回 true 。

---

iterator

public Iterator<E> iterator()

返回在队列中的元素上进行迭代的迭代器。迭代器并不以任意特定的顺序返回元素。

指定者：

接口 Iterable<E> 中的 iterator

指定者：

接口 Collection<E> 中的 iterator

指定者：

类 AbstractCollection<E> 中的 iterator

返回：

在队列中的元素上进行迭代的迭代器。

---

size

public int size()

从类 AbstractCollection 复制的描述

返回此 collection 中的元素数。如果该 collection 包含多于 Integer.MAX_VALUE 的元素，则返回 Integer.MAX_VALUE 。

指定者：

接口 Collection<E> 中的 size

指定者：

类 AbstractCollection<E> 中的 size

返回：

此 collection 中的元素数。

---

clear

public void clear()

从优先级队列中移除所有元素。此调用返回后队列为空。

指定者：

接口 Collection<E> 中的 clear

覆盖：

类 AbstractQueue<E> 中的 clear

---

poll

public E poll()

从接口 Queue 复制的描述

检索并移除此队列的头，如果此队列为空，则返回 null 。

指定者：

接口 Queue<E> 中的 poll

返回：

队列的头，或者如果此队列为空，则返回 null 。

---

comparator

public Comparator<? super E> comparator()

返回用于排序集合的比较器，或者如果此集合根据其元素的自然顺序排序（使用 Comparable ），则返回 null 。

返回：

用于排序集合的比较器，或者如果此集合根据其元素的自然顺序排序，则返回 null 。