Java-Collections Framework学习与总结-PriorityQueue
开发中有时会遇到这样的情况。要求某个调度器去调度一些任务，这些任务放在队列里。任务本身有优先级，调度器要按照优先级去调度队列里的任务，当然也会有新任务不断加入到队列中。
可以类比操作系统调度程序，操作系统要调度某个进程，简单的说会根据某种优先级进行调度(比如某些情况下，先执行时间较短的任务，保证短任务尽快结束。)
所以期望有这样一种数据结构，首先它是一个队列，可以从这个队列中不断取出优先级最高的(也可以认为是最大的或者最小的，因为本质是通过比较决定。)元素。也可以不断的将新元素添加到这个队列。
这种数据结构就叫做优先队列。优先队列的实现方式有很多，但好的实现应该保证关键的操作(如将一个元素放入队列；将优先级最大的元素移出队列等)比较高效。有一种数据结构可以比较高效的实现优先队列，这种数据结构叫二叉堆(binary heap)。
二叉堆形式上是一棵完全二叉树，它的一个重要性质是堆序性，即对于堆中任一个节点n，节点n上的元素e都要小于或等于其子节点(左右两个儿子节点)上的元素。
上图中，图(1)和图(2)都是完全二叉树，但只有图(1)是二叉堆，因为图(2)中39大于25和29，不满足堆序性。
接下来看一下，这样的数据结构怎么支持优先队列的操作。
先考虑下获取最小元素的操作，因为最小元素就在树的根节点，所以这个操作只要返回树根节点的元素就行了，操作时间为常数时间。
在看一下添加一个元素的操作，因为二叉堆是一个完全二叉树，所以添加一个元素时首先要将元素添加到完全二叉树的下一个节点上，然后进行一些调整来保证堆序性。
假设要在图(1)中的二叉堆中添加新元素2，图(2)中标出了新元素2要加入的节点，将元素添加到此节点上，就完成了第一步添加操作，如图(3)。接下来是调整操作，为了保证堆序性。首先将新节点与其父节点进行比较(比较元素大小)，如果父节点元素小于新节点元素，那么交换新节点和父节点的元素，如图(4)。然后依次类推，继续向上比较，如图(5)、图(6)，一直到当前比较节点大于其父节点，或者没有父节点(到达根节点)为止。
可以看到，上图中新添元素向上移动过程中比较次数正好是这个完全二叉树的高，而且上图表示是最差情况(需要比较并移动的次数最多)。所以在二叉堆中新添一个元素的操作时间是O(logN)。
最后看一下移除最小元素的操作(等同于优先级最大元素出队列操作)。因为最小元素就在树根，所以将最小元素移除很简单。但移除之后需要做一系列调整，以保证二叉堆的堆序性。
当我们移除最小元素时，如图(1)。先将最小元素移除(移除根节点上的元素)，并将完全二叉树的最后节点删除，保留其元素(这一步相当于在二叉堆中删除一个元素时，缩短其长度)，如图(2)。由于树根没有元素，我们需要把下面的元素向上移动。在移动过程中需要保证堆序性，所以当树根没有元素时，将树根的两个儿子节点中较小的一个中的元素放到树根节点中，如图(3)。现在树根的左子节点元素为空了，我们以同样的方式对其进行处理，直到某个空节点的两个子节点中的元素都大于图(1)中的保留元素27，或者某个空节点没有子节点为止，然后将保留元素27放到这个空节点中。(上图中没有表现出现第一种情况，假设图(4)中空节点下面的两个子节点所带元素为30和34，再想一下上图中的流程)。
这个过程删掉了最小元素同时保证了堆序性，同时也可以看到这个操作的时间也是O(logN)。
以上是二叉堆可支持优先队列的主要操作，从中也可以看到，二叉堆只是把最小元素放在树根节点上，其他元素的顺序是无法保证的。(当然也可以把最大元素放到根节点，因为保证堆序性的过程基于比较。所以有最小堆和最大堆的说法)
有了二叉堆的理论基础，就可以看下java.util.PriorityQueue的源码了。
/** * Establishes the heap invariant (described above) in the entire tree, * assuming nothing about the order of the elements prior to the call. */ private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); }