一.优先队列的应用
优先队列在程序开发中并不少见。 例如，操作系统调度进程时可以运行的算法之一是使用优先队列，新的进程是fork ) )出来后，首先将其放置在队列的末尾。 操作系统内部的调度程序不断从该优先队列中检索出高优先顺序进程的执行。 爬虫系统在运行时也经常需要从一个优先顺序队列中循环取出优先顺序高的任务来获取。 如果未对这些任务应用优先级排序，则可能会导致系统出现故障，例如操作系统中的低优先级进程持续消耗资源，而高优先级进程始终在队列中等待。 此外，优先队列在贪心算法中也有一些应用。
二.优先队列的实现原理
优先队列的实现方式使用双叉堆栈的结构，必须满足以下两个性质(Heap property )。 这里以小的天花板堆栈为例进行说明。1 .任何节点的值都在其子节点的值以下。 2 .所有节点从上到下，从左到右填充。 也就是说，是完全的二叉树。
基于这两个定律，叉堆在安装中经常使用一个数组。 以下，讨论叉堆(优先队列)在JDK中的安装。
研究
三.优先队列在JDK中的实现方式
源代码的最佳方法是debug。 看每一步变量的变化，可以很容易地写Demo。 让debug进入源代码进行查看：
在这里，我们很容易创建优先队列，然后向其中添加三个元素。 代码的第一行可以有断点。 如果使用的是Eclipse编辑器，则下次按F5键进入源代码。
代码已经运行到这里，优先级队列将调用自己的过载构造函数。 第一个参数是数组的缺省大小，第二个参数是元素比较的比较器。 这个Demo比较简单。
使用优先队列时，还可以实现自己的比较器。
公共资源队列(初始容量、
比较器？ 超级比较器) {
//note : thisrestrictionofatleastoneisnotactuallyneeded，
//butcontinuesfor 1.5兼容性
if (初始容量1 ) )。
thrownewillegalargumentexception (；
this.queue=新建对象；
this .比较器=比较器；
}接下来，我们来研究添加元素时的出价操作。
公共基金(e ) {
if (e==空值) )。
左右两侧空点互联(；
//记录队列被更改的次数
模具计数；
inti=大小；
if (I=队列长度) ) )。
//扩展
grow(I1；
//增加元素的个数
size=i 1；
if(I==0) ) )。
//第一次添加元素，直接放在第0个位置就可以了
队列=e；
else
//要素放在最后，需要进行过滤
移位上升(I，e )；
返回真；
{1}逐行说明一下。 首先，offer方法判断参数是否为空，如果不为空，则使变量modCount递增，modCount记录队列被更改的次数。 然后判断数组是否越界，越界时用grow扩展，然后添加元素，如果当前元素为0，则直接将元素放置在数组的第一个位置，否则进行siftUp操作
私有语音容量(最小容量) {
int old容量=队列长度；
//双精度if small； else grow by 50%
新内容
y = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //元素拷贝 queue = Arrays.copyOf(queue, newCapacity);上面的代码对队列扩容，源码中注释也很清晰，首先判断当前的数组大小是否足够小(<64)
如果足够小则将大小扩充为2倍，否则将原大小加上50%。需要注意的是，这里最后做了一个大小是否溢出的判断。
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }如果需要扩容的大小已经<0了，显然已经溢出了，在这里抛出了OutOfMemory的异常。
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; }为了保证优先队列的性质1，在插入每个元素时都需要与该节点父亲进行比较，找到其正确位置，有些数据结构书中，这个操作被称为上滤(percolate up)。
入队操作已经说完了，接下来是出队操作，即poll()操作：
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; }这个方法首先将数组第一个元素作为结果，(因为如果是小顶堆的话堆顶始终是最小元素)，并将队列的最后一个元素放到第一个位置，最后用siftDown做一些调整，保证队列的性质，这个操作被称为下滤(percolate down)。
private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; //这里k必须有孩子，故叶节点需要比较 while (k < half) { //以下几行代码到较小的那个儿子,用变量c表示 int child = (k << 1) + 1; //这里假设左儿子比较小 Object c = queue[child]; int right = child + 1; //左右儿子比较，如果右儿子小则将c赋值为右儿子 if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) c = queue[child = right]; //如果x比小儿子还小，说明k就是正确位置 if (comparator.compare(x, (E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = x; }如上图，下滤过程中k不断与其儿子进行比较，如果满足优先队列的顺序性，则break出循环。