JavaTM 2 Platform
Standard Ed. 5.0

java.util
类 PriorityQueue<E>

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)。

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

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

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

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

实现注意事项:此实现为插入方法(offerpollremove()add 方法)提供 O(log(n)) 时间;为 remove(Object)contains(Object) 方法提供线性时间;为检索方法(peekelementsize)提供固定时间。

此类是 Java Collections Framework 的成员。

从以下版本开始:
1.5
另请参见:
序列化表格

构造方法摘要
PriorityQueue()
          使用默认的初始容量(11)创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(Collection<? extends E> c)
          创建包含指定集合中元素的 PriorityQueue
PriorityQueue(int initialCapacity)
          使用指定的初始容量创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
          使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器来排序其元素。
PriorityQueue(PriorityQueue<? extends E> c)
          创建包含指定集合中元素的 PriorityQueue
PriorityQueue(SortedSet<? extends E> c)
          创建包含指定集合中元素的 PriorityQueue
 
方法摘要
 boolean add(E o)
          向队列中添加指定的元素。
 void clear()
          从优先级队列中移除所有元素。
 Comparator<? super E> comparator()
          返回用于排序集合的比较器,如果此集合根据其元素的自然顺序排序(使用 Comparable),则返回 null
 Iterator<E> iterator()
          返回在队列中的元素上进行迭代的迭代器。
 boolean offer(E o)
          向优先级队列中插入指定的元素。
 E peek()
          检索,但是不移除此队列的头,如果此队列为空,则返回 null
 E poll()
          检索并移除此队列的头,如果此队列为空,则返回 null
 boolean remove(Object o)
          从队列中移除指定元素的单个实例(如果其存在)。
 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(int initialCapacity)
使用指定的初始容量创建一个 PriorityQueue,并根据其自然顺序来排序其元素(使用 Comparable)。

参数:
initialCapacity - 优先级队列的初始容量。
抛出:
IllegalArgumentException - 如果 initialCapacity 小于 1。

PriorityQueue

public PriorityQueue(int initialCapacity,
                     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(E o)
向优先级队列中插入指定的元素。

指定者:
接口 Queue<E> 中的 offer
参数:
o - 要插入的元素。
返回:
true
抛出:
ClassCastException - 如果根据优先级队列的排序规则无法将指定的元素与当前优先级队列中存在的元素进行比较。
NullPointerException - 如果指定的元素为 null

peek

public E peek()
从接口 Queue 复制的描述
检索,但是不移除此队列的头,如果此队列为空,则返回 null

指定者:
接口 Queue<E> 中的 peek
返回:
队列的头,如果此队列为空,则返回 null

add

public boolean add(E o)
向队列中添加指定的元素。

指定者:
接口 Collection<E> 中的 add
覆盖:
AbstractQueue<E> 中的 add
参数:
o - 元素
返回:
true (按照 Collection.add 的通用协定)。
抛出:
NullPointerException - 如果指定的元素为 null
ClassCastException - 如果根据优先级队列的排序规则无法将指定的元素与当前优先级队列中存在的元素进行比较。

remove

public boolean remove(Object o)
从队列中移除指定元素的单个实例(如果其存在)。

指定者:
接口 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

JavaTM 2 Platform
Standard Ed. 5.0

提交错误或意见
有关更多的 API 参考资料和开发人员文档,请参阅 Java 2 SDK SE 开发人员文档。该文档包含更详细的、面向开发人员的描述,以及总体概述、术语定义、使用技巧和工作代码示例。

版权所有 2004 Sun Microsystems, Inc. 保留所有权利。 请遵守许可证条款。另请参阅文档重新分发政策