java.lang.Object java.util.AbstractCollection<E> java.util.AbstractQueue<E> java.util.PriorityQueue<E>
E
- collection 中所保存元素的类型。
public class PriorityQueue<E>
一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 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 的成员。
构造方法摘要 | |
---|---|
PriorityQueue() 使用默认的初始容量(11)创建一个 PriorityQueue ,并根据其自然顺序对元素进行排序。 |
|
PriorityQueue(Collection<? extends E> c) 创建包含指定 collection 中元素的 PriorityQueue 。 |
|
PriorityQueue(int initialCapacity) 使用指定的初始容量创建一个 PriorityQueue ,并根据其自然顺序对元素进行排序。 |
|
PriorityQueue(int initialCapacity, Comparator<? super E> comparator) 使用指定的初始容量创建一个 PriorityQueue ,并根据指定的比较器对元素进行排序。 |
|
PriorityQueue(PriorityQueue<? extends E> c) 创建包含指定优先级队列元素的 PriorityQueue 。 |
|
PriorityQueue(SortedSet<? extends E> c) 创建包含指定有序 set 元素的 PriorityQueue 。 |
方法摘要 | ||
---|---|---|
boolean |
add(E e) 将指定的元素插入此优先级队列。 |
|
void |
clear() 从此优先级队列中移除所有元素。 |
|
Comparator<? super E> |
comparator() 返回用来对此队列中的元素进行排序的比较器;如果此队列根据其元素的自然顺序进行排序,则返回 null 。 |
|
boolean |
contains(Object o) 如果此队列包含指定的元素,则返回 true 。 |
|
Iterator<E> |
iterator() 返回在此队列中的元素上进行迭代的迭代器。 |
|
boolean |
offer(E e) 将指定的元素插入此优先级队列。 |
|
E |
peek() 获取但不移除此队列的头;如果此队列为空,则返回 null。 |
|
E |
poll() 获取并移除此队列的头,如果此队列为空,则返回 null。 |
|
boolean |
remove(Object o) 从此队列中移除指定元素的单个实例(如果存在)。 |
|
int |
size() 返回此 collection 中的元素数。 |
|
Object[] |
toArray() 返回一个包含此队列所有元素的数组。 |
|
|
toArray(T[] a) 返回一个包含此队列所有元素的数组;返回数组的运行时类型是指定数组的类型。 |
从类 java.util.AbstractQueue 继承的方法 |
---|
addAll, element, remove |
从类 java.util.AbstractCollection 继承的方法 |
---|
containsAll, isEmpty, removeAll, retainAll, toString |
从类 java.lang.Object 继承的方法 |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
从接口 java.util.Collection 继承的方法 |
---|
containsAll, equals, hashCode, isEmpty, removeAll, retainAll |
构造方法详细信息 |
---|
public PriorityQueue()
PriorityQueue
,并根据其
自然顺序对元素进行排序。
public PriorityQueue(int initialCapacity)
PriorityQueue
,并根据其
自然顺序对元素进行排序。
initialCapacity
- 此优先级队列的初始容量
IllegalArgumentException
- 如果
initialCapacity
小于 1
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
PriorityQueue
,并根据指定的比较器对元素进行排序。
initialCapacity
- 此优先级队列的初始容量
comparator
- 用于对此优先级队列进行排序的比较器。如果该参数为
null
,则将使用元素的
自然顺序
IllegalArgumentException
- 如果
initialCapacity
小于 1
public PriorityQueue(Collection<? extends E> c)
PriorityQueue
。如果指定的 collection 是
SortedSet
的一个实例或者是另一个
PriorityQueue
,那么此优先级队列将根据相同顺序进行排序。否则,此优先级队列将根据元素的
自然顺序进行排序。
c
- collection,其元素要置于此优先级队列中
ClassCastException
- 如果根据优先级队列的排序规则无法比较指定 collection 中的各个元素
NullPointerException
- 如果指定 collection 或任何元素为 null
public PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue
。此优先级队列将根据与给定优先级队列相同的顺序进行排序。
c
- 优先级队列,其元素要置于此优先级队列中
ClassCastException
- 如果根据
c
的顺序无法比较
c
中的各个元素
NullPointerException
- 如果指定优先级队列或任何元素为 null
public PriorityQueue(SortedSet<? extends E> c)
PriorityQueue
。此优先级队列将根据与给定有序 set 相同的顺序进行排序。
c
- 有序 set,其元素将置于此优先级队列中
ClassCastException
- 如果根据有序 set 的顺序无法比较该有序 set 中的各个元素
NullPointerException
- 如果指定有序 set 或任何元素为 null
方法详细信息 |
---|
public boolean add(E e)
Collection<E>
中的
add
Queue<E>
中的
add
AbstractQueue<E>
中的
add
e
- 要添加的元素
true
(正如
Collection.add(E)
所指定的那样)
ClassCastException
- 如果根据优先级队列的顺序无法将指定元素与此优先级队列中当前元素进行比较
NullPointerException
- 如果指定的元素为 null
public boolean offer(E e)
e
- 要添加的元素
true
(正如
Queue.offer(E)
所指定的那样)
ClassCastException
- 如果根据优先级队列的顺序无法将指定元素与此优先级队列中当前元素进行比较
NullPointerException
- 如果指定元素为 null
public E peek()
public boolean remove(Object o)
o.equals(e)
的元素
e
,则移除一个这样的元素。当且仅当此队列包含指定的元素(或者此队列由于调用而发生更改),则返回
true
。
Collection<E>
中的
remove
AbstractCollection<E>
中的
remove
o
- 要从此队列中移除的元素(如果存在)
true
public boolean contains(Object o)
true
。更确切地讲,当且仅当此队列至少包含一个满足
o.equals(e)
的元素
e
时,才返回
true
。
Collection<E>
中的
contains
AbstractCollection<E>
中的
contains
o
- 要检查是否包含于此队列的对象
true
public Object[] toArray()
由于此队列并不维护对返回数组的任何引用,因而它将是“安全的”。(换句话说,此方法必须分配一个新数组)。因此,调用者可以随意修改返回的数组。
此方法充当基于数组的 API 与基于 collection 的 API 之间的桥梁。
Collection<E>
中的
toArray
AbstractCollection<E>
中的
toArray
public <T> T[] toArray(T[] a)
如果指定数组能容纳队列,且有剩余空间(即数组比队列元素多),则紧跟在 collection 末尾的数组元素将被设置为 null
。
像 toArray()
方法一样,此方法充当基于数组 的 API 与基于 collection 的 API 之间的桥梁。进一步说,此方法允许对输出数组的运行时类型进行精确控制,在某些情况下,可以用来节省分配开销。
假定 x 是只包含字符串的一个已知队列。以下代码可以用来将该队列转储到一个新分配的 String 数组:
String[] y = x.toArray(new String[0]);注意, toArray(new Object[0]) 和 toArray() 在功能上是相同的。
Collection<E>
中的
toArray
AbstractCollection<E>
中的
toArray
a
- 存储此队列元素的数组(如果该数组足够大);否则,将为此分配一个具有相同运行时类型的新数组。
如果指定数组的运行时类型不是此队列每个元素的运行时类型的子类型
NullPointerException
- 如果指定数组为 null
public Iterator<E> iterator()
Iterable<E>
中的
iterator
Collection<E>
中的
iterator
AbstractCollection<E>
中的
iterator
public int size()
Collection
复制的描述
Collection<E>
中的
size
AbstractCollection<E>
中的
size
public void clear()
Collection<E>
中的
clear
AbstractQueue<E>
中的
clear
public E poll()
public Comparator<? super E> comparator()
null
。
null