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

基于优先级堆的无界优先级队列。优先级队列的元素根据它们的自然顺序或在队列构建时提供的Comparator进行排序，具体取决于使用哪个构造函数。优先级队列不允许null元素。依赖于自然顺序的优先级队列也不允许插入不可比较的对象（这样做可能会导致ClassCastException）。

此队列的头部是根据指定顺序的最小元素。如果多个元素具有相同的最小值，则头部是这些元素之一 -- 平局会被任意打破。队列检索操作poll、remove、peek和element访问队列头部的元素。

优先级队列是无界的，但具有内部容量来控制用于存储队列元素的数组的大小。它的容量始终至少与队列大小一样大。随着元素被添加到优先级队列，其容量会自动增长。增长策略的细节未指定。

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

请注意，此实现不是同步的。如果任何线程修改队列，则不应同时访问PriorityQueue实例的多个线程。相反，请使用线程安全的PriorityBlockingQueue类。

实现说明: 此实现为入队和出队方法(offer、poll、remove()和add)提供O(log(n))时间；为remove(Object)和contains(Object)方法提供线性时间；为检索方法(peek、element和size)提供常数时间。

此类是Java集合框架的成员。

自 JDK 版本:

1.5

参见:

Constructor Summary

Constructors

Constructor

Description

PriorityQueue()

创建一个具有默认初始容量（11）的PriorityQueue，根据其自然顺序对其元素进行排序。

PriorityQueue(int initialCapacity)

创建一个具有指定初始容量的PriorityQueue，根据其自然顺序对其元素进行排序。

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

创建一个具有指定初始容量的PriorityQueue，根据指定的比较器对其元素进行排序。

PriorityQueue(Collection<? extends E> c)

创建一个包含指定集合中元素的PriorityQueue。

PriorityQueue(Comparator<? super E> comparator)

创建一个具有默认初始容量且其元素根据指定比较器排序的PriorityQueue。

PriorityQueue(PriorityQueue<? extends E> c)

创建一个包含指定优先级队列中元素的PriorityQueue。

PriorityQueue(SortedSet<? extends E> c)

创建一个包含指定排序集中元素的PriorityQueue。
Method Summary

Modifier and Type

Method

Description

boolean

add(E e)

将指定元素插入此优先级队列。

void

clear()

从此优先级队列中移除所有元素。

Comparator<? super E>

comparator()

返回用于对此队列中的元素进行排序的比较器，如果此队列根据其元素的自然顺序排序，则返回null。

boolean

contains(Object o)

如果此队列包含指定元素，则返回true。

void

forEach(Consumer<? super E> action)

对Iterable的每个元素执行给定操作，直到所有元素都已处理完或操作引发异常。

Iterator<E>

iterator()

返回此队列中元素的迭代器。

boolean

offer(E e)

将指定元素插入此优先级队列。

E

peek()

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

E

poll()

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

boolean

remove(Object o)

如果存在，则从此队列中移除指定元素的单个实例。

boolean

removeAll(Collection<?> c)

移除此集合中也包含在指定集合中的所有元素（可选操作）。

boolean

removeIf(Predicate<? super E> filter)

移除此集合的所有满足给定谓词的元素。

boolean

retainAll(Collection<?> c)

仅保留此集合中包含在指定集合中的元素（可选操作）。

int

size()

返回此集合中的元素数。

final Spliterator<E>

spliterator()

创建一个延迟绑定和快速失败的Spliterator，用于遍历此队列中的元素。

Object[]

toArray()

返回一个包含此队列中所有元素的数组。

<T> T[]

toArray(T[] a)

返回一个包含此队列中所有元素的数组；返回数组的运行时类型是指定数组的类型。

Methods declared in class java.util.AbstractQueue
addAll, element, remove

Methods declared in class java.util.AbstractCollection
containsAll, isEmpty, toString

Methods declared in class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods declared in interface java.util.Collection
containsAll, equals, hashCode, isEmpty, parallelStream, stream, toArray

Constructor Details
- PriorityQueue
  
  public PriorityQueue()
  
  创建一个具有默认初始容量（11）的PriorityQueue，根据其自然顺序对其元素进行排序。
- PriorityQueue
  
  public PriorityQueue(int initialCapacity)
  
  创建一个具有指定初始容量的PriorityQueue，根据其自然顺序对其元素进行排序。
  
  参数:
  
  initialCapacity - 此优先级队列的初始容量
  
  抛出:
  
  IllegalArgumentException - 如果initialCapacity小于1
- PriorityQueue
  
  public PriorityQueue(Comparator<? super E> comparator)
  
  创建一个具有默认初始容量且其元素根据指定比较器排序的PriorityQueue。
  
  参数:
  
  comparator - 将用于对此优先级队列排序的比较器。如果为null，则将使用元素的自然顺序。
  
  自 JDK 版本:
  
  1.8
- PriorityQueue
  
  public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
  
  创建一个具有指定初始容量的PriorityQueue，根据指定比较器对其元素进行排序。
  
  参数:
  
  initialCapacity - 此优先级队列的初始容量
  
  comparator - 将用于对此优先级队列排序的比较器。如果为null，则将使用元素的自然顺序。
  
  抛出:
  
  IllegalArgumentException - 如果initialCapacity小于1
- PriorityQueue
  
  public PriorityQueue(Collection<? extends E> c)
  
  创建一个包含指定集合中元素的PriorityQueue。如果指定的集合是SortedSet的实例或是另一个PriorityQueue，则此优先级队列将根据相同的顺序进行排序。否则，此优先级队列将根据其元素的自然顺序进行排序。
  
  参数:
  
  c - 要放入此优先级队列中的元素的集合
  
  抛出:
  
  ClassCastException - 如果指定集合的元素无法根据优先级队列的排序进行比较
  
  NullPointerException - 如果指定集合或其任何元素为null
- PriorityQueue
  
  public PriorityQueue(PriorityQueue<? extends E> c)
  
  创建一个包含指定优先级队列中元素的PriorityQueue。此优先级队列将根据给定优先级队列的相同顺序进行排序。
  
  参数:
  
  c - 要放入此优先级队列中的元素的优先级队列
  
  抛出:
  
  ClassCastException - 如果c的元素无法根据c的排序进行比较
  
  NullPointerException - 如果指定的优先级队列或其任何元素为null
- PriorityQueue
  
  public PriorityQueue(SortedSet<? extends E> c)
  
  创建一个包含指定排序集中元素的PriorityQueue。此优先级队列将根据给定排序集的相同顺序进行排序。
  
  参数:
  
  c - 要放入此优先级队列中的元素的排序集合
  
  抛出:
  
  ClassCastException - 如果指定排序集合的元素无法根据排序集合的顺序进行比较
  
  NullPointerException - 如果指定的排序集合或其任何元素为null
Method Details
- add
  
  public boolean add(E e)
  
  将指定的元素插入此优先级队列。
  
  指定者:
  
  add 在接口 Collection<E>
  
  指定者:
  
  add 在接口 Queue<E>
  
  覆盖:
  
  add 在类 AbstractQueue<E>
  
  参数:
  
  e - 要添加的元素
  
  返回:
  
  true (如Collection.add(E)中指定的)
  
  抛出:
  
  ClassCastException - 如果指定的元素无法根据优先级队列的顺序与当前在此优先级队列中的元素进行比较
  
  NullPointerException - 如果指定的元素为null
- offer
  
  public boolean offer(E e)
  
  将指定的元素插入此优先级队列。
  
  指定者:
  
  offer 在接口 Queue<E>
  
  参数:
  
  e - 要添加的元素
  
  返回:
  
  true (如Queue.offer(E)中指定的)
  
  抛出:
  
  ClassCastException - 如果指定的元素无法根据优先级队列的顺序与当前在此优先级队列中的元素进行比较
  
  NullPointerException - 如果指定的元素为null
- peek
  
  public E peek()
  
  从接口复制的描述: Queue
  
  检索但不移除此队列的头部元素；如果此队列为空，则返回null。
  
  指定者:
  
  peek 在接口 Queue<E>
  
  返回:
  
  此队列的头部元素，如果此队列为空则返回null
- remove
  
  public boolean remove(Object o)
  
  从此队列中移除指定元素的单个实例（如果存在）。更正式地说，如果此队列包含一个或多个这样的元素e，使得o.equals(e)，则移除一个元素。仅当此队列包含指定元素时返回true（或者等效地，如果此队列由于调用而更改）。
  
  指定者:
  
  remove 在接口 Collection<E>
  
  覆盖:
  
  remove 在类 AbstractCollection<E>
  
  参数:
  
  o - 如果存在，则从此队列中移除的元素
  
  返回:
  
  如果此队列由于调用而更改，则返回true
- contains
  
  public boolean contains(Object o)
  
  如果此队列包含指定元素，则返回true。更正式地说，仅当此队列包含至少一个元素e，使得o.equals(e)时，返回true。
  
  指定者:
  
  contains 在接口 Collection<E>
  
  覆盖:
  
  contains 在类 AbstractCollection<E>
  
  参数:
  
  o - 要在此队列中检查包含性的对象
  
  返回:
  
  如果此队列包含指定元素，则返回true
- toArray
  
  public Object[] toArray()
  
  返回一个包含此队列中所有元素的数组。元素没有特定的顺序。
  返回的数组将是“安全”的，因为此队列不维护对它的任何引用。（换句话说，此方法必须分配一个新数组）。因此，调用者可以自由修改返回的数组。
  
  此方法充当基于数组和基于集合的API之间的桥梁。
  
  指定者:
  
  toArray 在接口 Collection<E>
  
  覆盖:
  
  toArray 在类 AbstractCollection<E>
  
  返回:
  
  包含此队列中所有元素的数组
- toArray
  
  public <T> T[] toArray(T[] a)
  返回一个包含此队列中所有元素的数组；返回数组的运行时类型是指定数组的类型。返回的数组元素没有特定的顺序。如果队列适合指定的数组，则将其返回。否则，将使用指定数组的运行时类型和此队列的大小分配一个新数组。
  如果队列适合指定数组并有多余空间（即，数组的元素比队列多），则数组中紧随集合末尾的元素设置为null。
  
  与toArray()方法一样，此方法充当基于数组和基于集合的API之间的桥梁。此外，此方法允许精确控制输出数组的运行时类型，并且在某些情况下可以用于节省分配成本。
  
  假设x是一个已知仅包含字符串的队列。以下代码可用于将队列转储到新分配的String数组中：
  
  String[] y = x.toArray(new String[0]);
  请注意，toArray(new Object[0])在功能上与toArray()相同。
  指定者:
  
  toArray 在接口 Collection<E>
  
  覆盖:
  
  toArray 在类 AbstractCollection<E>
  
  类型参数:
  
  T - 包含集合的数组的组件类型
  
  参数:
  
  a - 如果足够大，则将队列的元素存储在其中；否则，将为此目的分配相同运行时类型的新数组。
  
  返回:
  
  包含此队列中所有元素的数组
  
  抛出:
  
  ArrayStoreException - 如果指定数组的运行时类型不是此队列中每个元素的运行时类型的超类型
  
  NullPointerException - 如果指定数组为null
- iterator
  
  public Iterator<E> iterator()
  
  返回此队列中元素的迭代器。迭代器不以任何特定顺序返回元素。
  
  指定者:
  
  iterator 在接口 Collection<E>
  
  指定者:
  
  iterator 在接口 Iterable<E>
  
  指定者:
  
  iterator 在类 AbstractCollection<E>
  
  返回:
  
  此队列中元素的迭代器
- size
  
  public int size()
  
  从接口复制的描述: Collection
  
  返回此集合中的元素数量。如果此集合包含的元素超过Integer.MAX_VALUE个，则返回Integer.MAX_VALUE。
  
  指定由：
  
  size 在接口 Collection<E>中
  
  返回：
  
  此集合中的元素数量
- clear
  
  public void clear()
  
  从此优先级队列中删除所有元素。调用返回后，队列将为空。
  
  指定由：
  
  clear 在接口 Collection<E>中
  
  覆盖：
  
  clear 在类 AbstractQueue<E>中
- poll
  
  public E poll()
  
  从接口中复制的描述： Queue
  
  检索并删除此队列的头部，如果此队列为空，则返回null。
  
  指定由：
  
  poll 在接口 Queue<E>中
  
  返回：
  
  此队列的头部，如果此队列为空则返回null
- comparator
  
  public Comparator<? super E> comparator()
  
  返回用于对此队列中的元素排序的比较器，如果此队列根据其元素的自然排序排序，则返回null。
  
  返回：
  
  用于对此队列排序的比较器，如果此队列根据其元素的自然排序排序则返回null
- spliterator
  
  public final Spliterator<E> spliterator()
  
  创建一个在此队列中的元素上执行延迟绑定和快速失败的Spliterator。Spliterator不按任何特定顺序遍历元素（不报告ORDERED特征）。
  Spliterator报告Spliterator.SIZED、Spliterator.SUBSIZED和Spliterator.NONNULL。重写实现应记录其他特征值的报告。
  
  指定由：
  
  spliterator 在接口 Collection<E>中
  
  指定由：
  
  spliterator 在接口 Iterable<E>中
  
  返回：
  
  在此队列中的元素上的Spliterator
  
  自1.8起
- removeIf
  
  public boolean removeIf(Predicate<? super E> filter)
  
  从接口中复制的描述： Collection
  
  删除满足给定谓词的此集合的所有元素。在迭代期间抛出的错误或运行时异常将被传递给调用者。
  
  指定由：
  
  removeIf 在接口 Collection<E>中
  
  参数：
  
  filter - 返回true以删除元素的谓词
  
  返回：
  
  如果删除了任何元素则返回true
  
  抛出：
  
  NullPointerException - 如果指定的过滤器为null
- removeAll
  
  public boolean removeAll(Collection<?> c)
  
  从类中复制的描述： AbstractCollection
  
  删除此集合中也包含在指定集合中的所有元素（可选操作）。调用返回后，此集合将不包含与指定集合共有的任何元素。
  指定由：
  
  removeAll 在接口 Collection<E>中
  
  覆盖：
  
  removeAll 在类 AbstractCollection<E>中
  
  参数：
  
  c - 包含要从此集合中删除的元素的集合
  
  返回：
  
  如果此集合由于调用而更改则返回true
  
  抛出：
  
  NullPointerException - 如果此集合包含一个或多个null元素且指定的集合不支持null元素（可选）或指定的集合为null
  
  参见：
  
  AbstractCollection.remove(Object)
  
  AbstractCollection.contains(Object)
- retainAll
  
  public boolean retainAll(Collection<?> c)
  
  从类中复制的描述： AbstractCollection
  
  仅保留此集合中包含在指定集合中的元素（可选操作）。换句话说，从此集合中删除不包含在指定集合中的所有元素。
  指定由：
  
  retainAll 在接口 Collection<E>中
  
  覆盖：
  
  retainAll 在类 AbstractCollection<E>中
  
  参数：
  
  c - 包含要在此集合中保留的元素的集合
  
  返回：
  
  如果此集合由于调用而更改则返回true
  
  抛出：
  
  NullPointerException - 如果此集合包含一个或多个null元素且指定的集合不允许null元素（可选）或指定的集合为null
  
  参见：
  
  AbstractCollection.remove(Object)
  
  AbstractCollection.contains(Object)
- forEach
  
  public void forEach(Consumer<? super E> action)
  
  从接口中复制的描述： Iterable
  
  对Iterable的每个元素执行给定操作，直到所有元素都已处理或操作引发异常。如果指定了迭代顺序，则按照迭代顺序执行操作。操作引发的异常将传递给调用者。
  如果操作执行会修改元素的底层来源并产生副作用，则此方法的行为是未指定的，除非覆盖类已指定了并发修改策略。
  
  指定由：
  
  forEach 在接口 Iterable<E>中
  
  参数：
  
  action - 要对每个元素执行的操作
  
  抛出：
  
  NullPointerException - 如果指定的操作为null

Class PriorityQueue<E>

Constructor Summary

Method Summary

Methods declared in class java.util.AbstractQueue

Methods declared in class java.util.AbstractCollection

Methods declared in class java.lang.Object

Methods declared in interface java.util.Collection

Constructor Details

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

Method Details

add

offer

peek

remove

contains

toArray

toArray

iterator

size

clear

poll

comparator

spliterator

removeIf

removeAll

retainAll

forEach