在讲解PriorityQueue之前，需要先熟悉一个有序数据结构：最小堆。
最小堆是一种经过排序的完全二叉树，其中任一非终端节点数值均不大于其左孩子和右孩子节点的值。
可以得出结论，如果一棵二叉树满足最小堆的要求，那么，堆顶（根节点）也就是整个序列的最小元素。
最小堆的例子如下图所示：
可以注意到，20的两个子节点31、21，和它们的叔节点30并没有严格的大小要求。以广度优先的方式从根节点开始遍历，可以构成序列：
[10,20,30,31,21,32,70]
反过来，可以推演出，序列构成二叉树的公式是：对于序列中下标为i的元素，左孩子为left(i) = i*2 +1，右孩子为 right(i) = left(i)+1。
现在可以思考一个问题，对于给定的序列，如何让它满足最小堆的性质？
例如[20, 10, 12, 1, 7, 32, 9]，可以构成二叉树：
这里提供一个方法：
1、倒序遍历数列；
2、挨个进行沉降处理，沉降过程为：和左右子节点中的最小值比对，如果比最小值要大，则和该子节点交换数据，反之则不做处理，继续1过程；
3、沉降后的节点，再次沉降，直到叶子节点。
同时，因为下标在size/2之后的节点是叶子节点，无需比对，所以可以从size/2-1位置开始倒序遍历，节约执行次数。
应用该方法对之前的数列进行解析：
1、数列[20,10,12,1,7,32,9]长度为7，所以size/2 - 1 =2，倒序遍历过程是12 -> 10 ->20；
2、12的左孩子为32，右孩子为9，12>9，进行沉降，结果如下图所示：
3、10的左孩子为1，右孩子为7，10 > 1，进行沉降，结果如下图所示：
4、20的左孩子为1，右孩子为9，20 > 1，进行沉降，结果如下图所示：
5、20的左孩子为10，右孩子为7，20 > 7，进行沉降，得到最终结果：
满足最小堆的要求，此时，得出的序列为[1,7,9,10,20,32,12]。
该实现的流程也就是PriorityQueue的heapify方法的流程，heapify方法负责把序列转化为最小堆，也就是所谓的建堆。其源码如下所示：
private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); }
siftDown方法也就是之前提过的沉降。
siftDown(k,x)方法解析
siftDown这个方法，根据comparator成员变量是否为null，它的执行方式略有不同:
如果comparator不为null，调用comparator进行比较；
反之，则把元素视为Comparable进行比较;
如果元素不为Comparable的实现，则会抛出ClassCastException。
不论哪种，执行的算法是一样的，这里只做Comparator的源码解析：
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; }
注释已经解释清楚了代码的执行逻辑，其目的是把不满足最小堆条件的父节点一路沉到最底部。从以上代码可以看出，siftDown的时间复杂度不会超出O(logn)。
siftUp(k,x)方法解析
siftUp方法用于提升节点。新加入的节点一定在数列末位，为了让数列满足最小堆性质，需要对该节点进行提升操作。
和siftDown一样，它也有两种等效的实现路径，这里只做shifUpUsingComparator的解析：
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; }
节点的插入，是在数列的尾端的，它很可能比父节点要小，不满足最小堆的定义，所以，需要做上浮的操作。
这里提供一个例子帮助理解，有最小堆数列[10，20，30，40，30，50，70]，构成最小堆如下所示：
1、执行添加19，变为：
2、19<40，与40交换位置：
3、19<20，与20交换位置：
4、19>10，终止上浮操作，最后得到的数列为：
[10，19，30，20，30，50，70，40]
满足了最小堆的性质。
