【Java数据结构】优先队列（堆）

本文参考链接：

• https://www.cnblogs.com/wmyskxz/p/9301021.html
• 《数据结构与算法分析——Java语言描述（第二版）》

0.序

虽然发送到打印机的作业一般被放到队列中，但这未必总是最好的做法。例如，可能有一项作业特别重要，因此希望只要打印机一有空闲就来处理这项作业。反之，若在打印机有空时正好有多个单页的作业及一项100页的作业等待打印，更合理的做法也许是最后处理长的作业，尽管它不是最后提交上来的。
类似地，在多用户环境中，操作系统调度程序必须决定在若干进程中运行哪个进程。一般一个进程只被允许运行一个固定的时间片。一种算法是使用一个队列。开始时作业被放到队列的末尾。调度程序将反复提取队列中的第一个作业并运行它，直到运行完毕。或者该作业的时间片用完，并在作业未运行完毕时把它放到队列末尾。这种策略一般并不太合适，因为一些很短的作业由于一味等待运行而要花费很长的时间去处理。一般说来，短的作业要尽可能快地结束，这一点很重要。因此在已经运行的作业当中这些短作业应该拥有优先权。此外，有些作业虽不短小，但很重要，也应该拥有优先权。
这种处理优先权的应用需要一类特殊的队列，称之为“优先队列（Priority Queue）”。

1.模型

优先队列也是一种队列，只不过不同的是，优先队列的出队顺序是按照优先级来的；在有些情况下，可能需要找到元素集合中的最小或者最大元素，可以利用优先队列ADT来完成操作，优先队列ADT是一种数据结构，它支持插入和删除最小值操作（返回并删除最小元素）或删除最大值操作（返回并删除最大元素）；
这些操作等价于队列的enQueue和deQueue操作，区别在于，对于优先队列，元素进入队列的顺序可能与其被操作的顺序不同，作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

除了操作系统外，优先队列还有许多的应用。在贪婪算法（greedy algorithm）的实现方面，优先队列也是很重要的，该算法通过反复求出最小元来进行操作。
如果最小键值元素拥有最高的优先级，那么这种优先队列叫作升序优先队列（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作降序优先队列（即总是先删除最大的元素）；由于这两种类型是对称的，所以只需要关注其中一种，如升序优先队列；

2.一些简单的实现

有几种明显的方法可以用于实现优先队列。我们可以使用一个简单链表在表头以O(1)执行插入操作，并遍历该链表以删除最小元，这又需要O(N)时间。另一种方法是始终让链表保持排序状态——这使得插入的代价高昂（O(N)）而deleteMin花费低廉（O(1)）。基于deleteMin的操作从不多于插入操作的事实，前者恐怕是更好的想法。
另一种实现优先队列的方法是使用二叉查找树，它对这两种操作的平均运行时间都是O(logN)。尽管插入是随机的，而删除则不是，但这个结论还是成立的。记住我们删除的唯一元素是最小元。反复除去左子树中的节点似乎会损害树的平衡，使得右子树加重。然而，右子树是随机的。在最坏情形下，即deleteMin将左子树删空的情形下，右子树拥有的元素最多也就是它应具有的两倍。这只是在期望的深度上加了一个小常数。注意，通过使用一棵平衡数，可以把这个界变成最坏情形的界；这将防止出现坏的插入序列。
使用查找树可能有些过分，因为它支持许许多多并不需要的操作。我们将要使用的基本的数据结构不需要链，它以最坏情形时间O(logN)支持上述两种操作。插入操作实际上将花费常数平均时间，若无删除操作的干扰，该结构的实现将以线性时间建立一个具有N项的优先队列。然后，我们将讨论如何实现优先队列以支持有效的合并。这个附加的操作似乎有些复杂，它显然需要使用链表的结构。
优先队列的实现时间复杂度如下表所示：

实现	插入	删除	寻找最小值
无序数组	1	1	N
无序链表	1	1	N
有序数组	N	1	1
有序链表	N	1	1
二叉查找树	logN（平均）	logN（平均）	logN（平均）
平衡二叉查找树	logN	logN	logN
二叉堆（下节介绍）	logN	logN	1

3.堆和二叉堆

1. 堆
堆是一颗具有特定性质的二叉树，堆的基本要求就是堆中所有结点的值必须大于或等于——findMax（或小于或等于——findMin）其子结点的值，这也称为堆的性质；堆还有另一个性质，就是当 h > 0 时，所有叶子结点都处于第 h 或 h - 1 层（其中 h 为树的高度，完全二叉树），也就是说，堆应该是一颗完全二叉树；

在下面的例子中，左边的树为堆（每个元素都大于其孩子结点的值），而右边的树不是堆（因为5大于其孩子结点2）

2. 二叉堆
在二叉堆中，每个结点最多有两个孩子结点，在实际应用中，二叉堆已经足够满足需求，因此接下来主要讨论二叉最小堆和二叉最大堆；

堆的表示：在描述堆的操作前，首先来看堆是怎样表示的，一种可能的方法就是使用数组，因为堆在形式上是一颗完全二叉树，用数组来存储它不会浪费任何空间，例如下图：

用数组来表示堆不仅不会浪费空间还具有一定的优势：

• 每个结点的左孩子为下标i的2倍：left child(i) = i * 2；每个结点的右孩子为下标i的2倍加1：right
  child(i) = i * 2 + 1
• 每个结点的父亲结点为下标的二分之一：parent(i) = i / 2，注意这里是整数除，2和3除以2都为1，大家可以验证一下；
• 注意：这里是把下标为0的地方空出来了的，主要是为了方便理解，如果0不空出来只需要在计算的时候把i值往右偏移一个位置就行了（也就是加1，大家可以试试，下面的演示也采取这样的方式）；
  （1）向堆中添加元素和Sift Up
  当插入一个元素到堆中时，它可能不满足堆的性质，在这种情况下，需要调整堆中元素的位置使之重新变成堆，这个过程称为堆化（heapifying）；在最大堆中，要堆化一个元素，需要找到它的父亲结点，如果不满足堆的基本性质则交换两个元素的位置，重复该过程直到每个结点都满足堆的性质为止，下面我们来模拟一下这个过程：
  下面我们在该堆中插入一个新的元素26：
  
  我们通过索引（上面的公式）可以很容易地找到新插入元素的父亲结点，然后比较它们的大小，如果新元素更大则交换两个元素的位置，这个操作就相当于把该元素**Shift up（上浮）**了一下：
  
  对应代码如下（摘自《数据结构与算法分析——Java语言描述》：

/**
 * Insert into the priority queue,maintaining heap order.
 * Duplicates are allowed
 * @param x the item to insert
**/
public void insert(Anytype x) {
	if(currentSize == array.length - 1) {
		enlargeArray(array.length *2 + 1);
		}
	//Percolate Up
	int hole = ++currentSize;
	for(;hole>1 && x.compareTo(array[hole/2]) > 0; hole /= 2 ) {
		array[hole] = array[hole/2];
		}
		array[hole] = x;
}

（2）deleteMax和Shift Down
如果理解了上述的过程，那么取出堆中的最大元素（堆顶元素）将变得容易，不过这里运用到一个小技巧，就是用最后一个元素替换掉栈顶元素，然后把最后一个元素删除掉，这样一来元素的总个数也满足条件，然后只需要把栈顶元素依次往下调整就好了，这个操作就叫做Shift Down（下沉）：

用最后元素替换掉栈顶元素，然后删除最后一个元素：

然后比较其孩子结点的大小：

如果不满足堆的条件，那么就跟孩子结点中较大的一个交换位置：

重复该步骤，直到16到达合适的位置：

完成取出最大元素的操作：

4.Java中的PriorityQueue

在Java中也实现了自己的优先队列java.util.PriorityQueue，与我们自己写的不同之处在于，Java中内置的为最小堆，然后就是一些函数名不一样，底层还是维护了一个Object类型的数组，大家可以查看有什么不同，另外如果想要把最小堆变成最大堆可以给PriorityQueue传入自己的比较器，例如：

// 默认为最小堆
PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(5);
pq.add(2);
pq.add(1);
pq.add(10);
pq.add(3);

while (!pq.isEmpty()) {
    System.out.println(pq.poll() + ", ");
}
System.out.println();
System.out.println("————————————————————————");

// 使用Lambda表达式传入自己的比较器转换成最大堆
PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> b - a);
pq2.add(5);
pq2.add(2);
pq2.add(1);
pq2.add(10);
pq2.add(3);

while (!pq2.isEmpty()) {
    System.out.println(pq2.poll() + ", ");
}