PriorityQueue 源码分析
PriorityQueue
一个无限的优先级队列基于一个优先级堆。优先级队列中的元素根据它们的Comparable自然顺序或通过在队列构造时提供的Comparator来排序。(如果有Comparator就根据Comparator来对元素进行排序，否则根据元素自己的Comparable来进行排序)。一个优先级队列不允许‘null’元素。一个依赖自然排序的优先级队列甚至不允许插入一个不可比较(non-comparable)的对象(如果你插入一个non-comparable对象，则会抛出一个ClassCastException异常)。
队列的头(head)元素是相对于指定顺序的最小的(least)元素。如果多个元素被绑为最小值，那么头元素是它们中的一个————绑定会被任意的破坏。队列的检索操作poll、remove、peek和element都会访问队列头(head)元素。
一个优先级队列是无限制的，但是它有一个内部的“capacity”管理着数组的大小，该数组用于存储队列的元素。它总是至少同队列大小一样大。当元素加到优先级队列中，它的容量会自动增加。并没有指定增长策略的细节。
该类和它的迭代器实现了Collection和Iterator接口所有可选的方法。迭代器提供的iterator()方法不保证遍历优先级队列的元素根据任何特别的顺序。如果你需要有序的遍历，考虑使用Arrays.sort(pq.toArray()). 注意，PriorityQueue类的实现是非同步的。如果任何一个线程修改队列，多线程不应该同时访问一个PriorityQueue实例。相反，应该使用线程安全的PriorityBlockingQueue类。
实现注意：该实现提供了O(log(n))时间复杂度对于入队和出队方法：offer、poll、remove()和add；线性的时间O(n)对于remove(object)和contains(object)方法；和常量的时间O(1)对于检索方法：peek、element和size。
属性
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access优先级队列表现为一个平衡二项堆(即，平衡二叉树)：queue[n]的两个儿子分别是queue[2n+1]和queue[2(n+1)]。优先级队列通过比较器(comparator)来排序，或者如果比较器为空则通过元素的自然顺序来排序：堆中每个节点n和n的每个后裔节点d，n <= d。假设队列是非空的，那么具有最低值的元素在queue[0]。
优先级队列的数据结构是一个平衡二叉树，并且数中所有的子节点必须大于等于父节点，而同一层子节点间无需维护大小关系。这样的结构性让优先级队列看起来像是一个最小堆。
父节点与子节点间的索引关系： ① 假设父节点为queue[n]，那么左孩子节点为queue[2n+1]，右孩子节点为queue[2(n+1)]。 ② 假设孩子节点(无论是左孩子节点还是右孩子节点)为queue[n]，n>0。那么父节点为queue[(n-1) >>> 1]
节点间的大小关系： ① 父节点总是小于等于孩子节点 ② 同一层孩子节点间的大小无需维护
叶子节点与非叶子节点： ① 一个长度为size的优先级队列，当index >= size >>> 1时，该节点为叶子节点。否则，为非叶子节点。"附"中会对该结论做个简单的证明。
/**
* 优先级队列元素的个数
*/
private int size = 0;
/**
* 优先级队列结构上被修改的次数。修改操作包括：clear()、offer(E)、poll()、removeAt(int)
*/
transient int modCount = 0; // non-private to simplify nested class access方法
- 添加节点
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}往优先级队列中插入元素，如果队列满了，则进行扩容。插入操作必要的话是会导致堆元素调整的，以满足父节点总是小于等于子节点的要求。 插入操作的时间复杂度为O(log(n));
通过siftUp方法来完成元素插入时的调整：siftUp(index, object)方法会升高待插入元素在树中的位置index，直到待插入的元素大于或等于它待插入位置的父节点
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}通过“int parent = (k - 1) >>> 1;”获取到当前要插入节点位置的父节点，比较父节点和待插入节点，如果待插入节点小于父节点，则将父节点插入到子节点的位置，然后在获取父节点的父节点循环上面的操作，直到待插入节点大于等于父节点，则在相应位置插入这个节点。最终保证代表优先级队列的平衡二叉树中，所有的子节点都大于它们的父节点，但同一层的子节点间并不需要维护大小关系。
图解“添加节点”步骤： 往一个空的优先级队列中依次插入“13”、“-3”、“20”、“-25” ① 插入“13”
② 插入“-3”
③ 插入“20”
④ 插入“-25”
- 获取优先级队列头结点
public E peek() {
return (size == 0) ? null : (E) queue[0];
}获取优先级队列头元素，也就是优先级队列中值最小的元素。 获取操作的时间复杂度为O(1)
- 删除节点
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}该删除操作的最坏耗时为：n + 2log(n); 所以该操作的的时间复杂度为O(n); indexOf(object)操作时间复杂度为O(n); removeAt(index)操作时间复杂度为O(log(n))
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}如果待删除节点位置为队列尾，则直接将队列尾位置置null。否则将队列尾节点前插以覆盖待删除节点位置的节点。 当待删除节点的位置为非叶子节点时，会进行一系列的节点调整，使得队尾节点在前插后能保证优先级队列数据结构的正确性。 当待删除节点的位置为叶子节点时，会先将队尾节点设置到待删除节点位置以使得队列中已经没有待删除节点了，然后再进行已经插入到新位置的队尾节点同它新父节点进行比较调整，以保证父节点总是小于等于子节点，即保证优先级队列数据结构的正确性。 当该方法进行siftUp操作来对节点进行结构调整后使得队尾节点最终并不是被设置到了待删除节点位置，这时就返回这个前插的队尾元素。因为这种情况下，删除操作会涉及到一个未访问的元素被移动到了一个已经访问过的节点位置。在迭代器操作中需要特殊处理。
通过siftDown方法来完成元素移除时的调整：siftDown(index, object)方法会降低待插入元素在树中的位置index，直到待插入的元素小于或等于它待插入位置的孩子节点。
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}因为在平衡二叉树中，叶子节点的个数总是大于等于前面所有非叶子节点个数之和。所有如果待删除元素的所在位置大于等于队列长度的一半，则说明待删除的节点是一个叶子节点，则直接将队列中最后一个节点值(注意，队列中最后一个节点一定也是叶子节点)设置到待删除节点所在位置。 如果待删除节点的位置小于队列长度的一半，则说明待删除的节点是一个非叶子节点。那么先取得待删除节点的子节点中小的那个子节点，将该子节点与队列中最后一个节点进行比较，如果子节点小于队列中最后一个节点，则将子节点值设置到待删除节点的位置，然后再次获取当前子节点的较小的子节点重复一样的操作，直到队列最后一个节点比较小的那个子节点还要小，则将队列最后一个节点值设置为这个子节点的父节点。最终保证代表优先级队列的平衡二叉树中，所有的父节点都小于等于它的子节点，但同一层的子节点间并不需要维护大小关系。
图解“删除节点”步骤： 假设有如下优先级队列：
情况一：删除“queue[7]=18”
情况二：删除“queue[2]=-23”
- 是否包含节点
public boolean contains(Object o) {
return indexOf(o) != -1;
}判断优先级队列中是否包含object对象。该方法的时间复杂度为：O(n)
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}- 移除并获取优先级队列头节点
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}移除并获取优先级队列头节点。该操作的时间复杂度为：O(log(n));
- 清除优先级队列中所有节点
modCount++;
for (int i = 0; i < size; i++)
queue[i] = null;
size = 0;
}清除优先级队列中的所有节点。该操作的事件复杂度为：O(n);
- 迭代器 优先级队列的迭代器并不保证遍历按照指定的顺序获取节点元素。这是因为当在迭代器中执行remove操作时，可能会涉及到一个未访问的元素被移动到了一个已经访问过的节点位置(删除操作时，当队尾节点被放置到待移除节点位置的情况下，需要调用siftUp方法，siftUp(index, object)方法会升高待插入元素在树中的位置index，直到待插入的元素大于或等于它待插入位置的父节点)。在迭代器操作中需要特殊处理。此时这些不幸的元素会在所有节点遍历完后才得以遍历。
附
- 证明“在平衡二叉树中，叶子节点的个数总是大于等于前面所有非叶子节点个数之和。” 一个平衡二叉树第N层节点数为：2^N 一个N层的平衡二叉树总节点数为：2^(N+1) -1； Sn = 2^0 + 2^1 + …… + 2^N 2*Sn = 2^1 + 2^2 + …… + 2^N + 2^(N+1) 将二个等式的左边和右边分别进行相减操作得到： (2-1)Sn = 2^(N+1) - 2^0 ==> Sn = 2^(N+1) -1; 所以一个N层的二叉平衡树除了叶子节点外的节点总数最大为：2^N -1； 因而2^N > 2^N -1，所以在满平衡二叉树下，叶子节点大于非叶子节点个数之和，当然在最后一层节点不满的情况下，叶子节点依旧大于等于所有非叶子之和。
后记
若文章有任何错误，望大家不吝指教:)