java 优先队列 PriorityQueue

一个基于优先级堆的*优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 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）提供固定时间。

构造函数和API：

构造方法摘要

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()            返回一个包含此队列所有元素的数组。
<T> T[]	toArray(T[] a)            返回一个包含此队列所有元素的数组；返回数组的运行时类型是指定数组的类型。

 

基于堆的优先队列，并没有将元素进行排序，而只是在利用最大堆或最小堆的性质在堆顶保存了最大值或者最小值，这样"插入" “删除”操作的代价都是lgn