数据结构与算法--优先队列和堆排序
在某些数据处理的例子中，总数据量太大，无法排序（甚至无法全部装进内存）。例如，需要从十亿个元素中选出最大的十个，你真的想把一个10亿规模的数组排序吗？但有了优先队列，你只用一个能存储十个元素的队列即可。具体做法是让元素一个个输入，只要优先队列的个数大于10，就不断删除最小元素，最后优先队列长度不大于10时停止删除，只剩10个自然就是所有元素中最大的10个了。
很多情况我们会收集一些元素，处理当前键值最大（或最小）的元素，然后再收集更多的元素，再处理当前最大的（或最小的）元素，这可以看成我们按照事件的优先级顺序来处理，生活中很多任务都是有优先级高低之分的，所以优先队列可以高效地处理这些情况。
优先队列支持两种操作：删除最大元素（或最小元素）和插入元素。我们将看到，删除最大元素的方法可以很简单地转换成删除最小元素。
优先队列的初级实现
有几种比较容易想到的思路。
1、基于无序数组（链表）
要删除最大元素，我们可以在代码中添加类似选择排序的内循环，将最大元素和边界元素交换，然后像pop方法那样删除它。
2、基于有序数组
另一种方法是在插入时就保证数组总是有序，像我们在符号表中基于有序数组的二分查找那样，先确定新元素在数组中的排名，然后所有比它大的元素都要向右移动一格以腾出空间，新元素插入后仍然保持着数组有序。最大元素和最小元素都在数组边界，删除操作也就变得相当简单了。
采用以上两种数据结构，实现很简单，但是在插入元素和删除最大元素这两个操作之一在最坏情况下需要线性时间来完成。接下来要学习的二叉堆结构能保证这两种操作都能更快执行。
堆的定义
在二叉堆的数组中，每个元素都要保证大于等于另外两个特定位置的元素。相应地，这些位置的元素又要大于等于数组中另外两个元素，以此类推。这种结构可以画成二叉树的样子。当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。根结点是堆有序的二叉树中的最大结点。这种堆称为大顶堆。相反地，我们可以定义小顶堆。
用完全二叉树表示二叉堆特别方便，如上图所示，每个结点都大于等于它的两个子结点。
用数组实现完全二叉树也很简单。因此我们可以直接用数组来实现二叉堆。具体方法是，数组的第一个位置a[0]不使用（为了计算简单），根结点存在a[1]，然后按照层级顺序将二叉树结点依次放入数组中。如下所示a[2]、a[3]是根结点的两个子结点，且都小于根结点，而a[2]和a[3]的子结点分别在在数组中的位置4、5和6、7，以此类推。
可以观察到规律：位置k的结点，其左子结点的位置是2k，右子结点的位置是2k+1；其父结点的位置是⌊k/2⌋。一棵大小为N的完全二叉树的高度是⌊lg N⌋。
我们希望在对堆的操作过程中（如插入元素和删除最大元素）都保持着堆的状态不被打破——即保持二叉堆中每个结点大于等于它两个子结点的状态，为此每次插入元素或者删除最大元素后都需要一些操作来恢复被打破的状态，这个过程称为堆的有序化。堆的有序化是通过上浮和下沉两个操作完成的。
由下至上的堆有序化——上浮
如果堆有序状态因为某个子结点比它的父结点更大而被打破，那么我们需要交换它和父结点的位置来恢复有序状态。交换后这个结点比它的两个子结点都大（一个是曾经的父结点，另外一个是原来父结点的子结点，更小）；如果交换后仍然比它的父结点大，就继续交换，直到该结点不再大于它的父结点为止。位置k的父结点的位置是⌊k/2⌋，记住这点就能轻松实现，我们为这个方法起一个形象的方法名swim（上浮）。
package Chap9;
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
// 优先队列元素个数
private int N;
public MaxPQ() {
// pq[0]没有使用
pq = (Key[]) new Comparable[2];
}
// 动态调整优先队列大小
private void resize(int max) {
Key[] temp = (Key[]) new Comparable[max];
// 有效值区间为[1, N]
for (int i = 1; i <= N; i++) {
temp[i] = pq[i];
}
pq = temp;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
private void swim(int k) {
// k = 1说明当前元素浮到了根结点，它没有父结点可以比较，也不能上浮了，所以k <= 1时候推出循环
while (k > 1 && less(k / 2, k)) {
swap(k/2, k);
// 上浮后，成为父结点，所以下标变成原父结点
k = k / 2;
}
}
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void swap(int i, int j) {
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
}
我们顺便定义了优先队列（基于大顶堆）的数据结构，用数组pq表示二叉堆。重点看swim方法的实现，和我们上面描述的操作完全一致，有一点注意while循环终止的条件中应该是k <= 1，因为k = 1时就说明当前结点浮到了根结点，它已经不能再上浮了，而且根结点也没有父结点和它比较。
由上至下的堆有序化——下沉
如果堆的有序状态因为某个结点变得比它的两个子结点或者其中之一更小而被打破了，可以先找到子结点中的较大者（它也比父结点大），将它与父结点交换来恢复堆，和上面一样，交换后可能还不是堆有序的状态，那就继续交换，直到它不小于它的两个子结点或者被交换到了堆的底部为止。位置为k的结点的左子结点和右子结点位置分别为2k 和2k + 1，由此可以写出如下代码，并为该方法起一个形象的方法名sink(下沉)。
private void sink(int k) {
// 父结点的位置k最大值为 N/2,若k有左子结点无右子结点，那么2k = N；若两个子结点都有，那么2k + 1 = N
// 有可能位置k只有左子结点，依然要比较，用2k + 1 <= N这个的条件不会执行比较，所以用2k <= N条件
while (2 * k <= N) {
int j = 2 * k;
// 可以取j = N -1,less(N -1, N);由于下标从1开始，所以pq[N]是有元素的
if (j < N && less(j,j+1)) {
// 右子结点比左子结点大 ，取右子结点的下标
j++;
}
// 左子结点或者右子结点和父结点比较
// 如果pq[k] >= pq[j]，即父结点大于等于较大子结点时，停止下沉
if (!less(k, j)) {
break;
}
// 否则交换
swap(k, j);
// 下沉后，下标变成与之交换的元素下标
k = j;
}
}
上浮和下沉的示意图如下
有了上面作铺垫，下面介绍插入和删除最大元素就简单多了。
插入和删除最大元素
对于数组，在数组末端添加元素是最简单的，为了维持堆有序的状态，添加到数组末端后，需要对其进行上浮操作，将它放到合适的位置。
最大元素在堆顶pq[1]，可以将其与数组中最后一个元素交换位置，因此最大元素到了数组末端，删除就方便多了。之后为了维持堆的有序，记得对换到堆顶的元素进行下沉操作，将它放到合适的位置。
插入和删除最大元素的操作示意图如下。
代码如下，实现中还添加了max()方法，返回最大元素——堆的根结点pq[1]
public void insert(Key key) {
// 由于下标从1开始算，存满时N就等于pq.length -1
if (N == pq.length - 1) {
resize(pq.length * 2);
}
// 注意是++N，从pq[1]开始存
pq[++N] = key;
swim(N);
}
public Key max() {
if (isEmpty()) {
throw new NoSuchElementException("优先队列为空");
}
return pq[1];
}
public Key delMax() {
if (isEmpty()) {
throw new NoSuchElementException("优先队列为空");
}
Key max = pq[1];
// 第一个和最后一个元素交换
swap(1, N);
// 删除位置N的元素，长度减1
pq[N--] = null;
// 删除后要恢复堆有序状态
sink(1);
if (N > 0 && N == pq.length / 4) {
resize(pq.length / 2);
}
return max;
}
delMax就一定需要注意，sink(1);的调用一定要在pq[N--] = null;之前，确保下沉时候，堆中已经没有那个元素且N已经减少1；否则，如果在删除之前下沉，被交换过去的堆顶元素下沉后有可能又回到了被交换前的位置（即数组末端），之后再删除就不是删除最大元素了。
要是觉得一个个insert元素很麻烦，可以新增一个构造方法，可以传入一个数组，数组中所有元素传递给pq，通过对pq中所有父结点进行下沉操作，之后数组就是堆有序的了。
// 传入数组，构造有序堆
public MaxPQ(Key... keys) {
pq = (Key[]) new Comparable[keys.length +1];
N = keys.length;
for (int i = 0; i < N; i++) {
pq[i+1] = keys[i];
}
for (int k = N / 2; k >= 1 ; k--) {
sink(k);
}
}
上面代码关键就在最后一个for循环，k = N / 2表示父结点的位置k最大值为 N/2，从这个结点开始由下至上对每个父结点进行下沉操作，最后当然是对根结点下沉，因此只要k >= 1循环就持续。
稍微测试下，下面将依次打印5、4、3。
public static void main(String[] args) {
MaxPQ<Integer> maxPQ = new MaxPQ<>(4,3,1,2,5);
System.out.println(maxPQ.delMax());
System.out.println(maxPQ.delMax());
System.out.println(maxPQ.delMax());
}
最后来看一个完整的插入删除操作，看看“堆”是怎么建立起来并维持着堆有序的状态的。
可以删除最小元素的MinPQ
MaxPQ转换成MinPQ相当简单！
MinPQ需要使用小顶堆，小顶堆即所有父结点的左右子结点都要小于等于它，和大顶堆的定义是对称的，所以只需将less替换成greater方法即可。
private boolean greater(int i, int j) {
return pq[i].compareTo(pq[j]) > 0;
}
就是将less中的<改成大于>，然后在所有使用less方法的地方换成greater就好了！MaxPQ的代码比较分散，这里给出MinPQ的完整实现和测试。
package Chap9;
import java.util.NoSuchElementException;
public class MinPQ<Key extends Comparable<Key>> {
private Key[] pq;
// 优先队列元素个数
private int N;
public MinPQ() {
// pq[0]没有使用
pq = (Key[]) new Comparable[2];
}
// 传入数组，构造有序堆
public MinPQ(Key... keys) {
pq = (Key[]) new Comparable[keys.length + 1];
N = keys.length;
for (int i = 0; i < N; i++) {
pq[i + 1] = keys[i];
}
for (int k = N / 2; k >= 1; k--) {
sink(k);
}
}
private void resize(int max) {
Key[] temp = (Key[]) new Comparable[max];
// 有效值区间为[1, N]
for (int i = 1; i <= N; i++) {
temp[i] = pq[i];
}
pq = temp;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert(Key key) {
// 由于下标从1开始算，存满时N就等于pq.length -1
if (N == pq.length - 1) {
resize(pq.length * 2);
}
// 注意是++N，从pq[1]开始存
pq[++N] = key;
swim(N);
}
public Key min() {
if (isEmpty()) {
throw new NoSuchElementException("优先队列为空");
}
return pq[1];
}
public Key delMin() {
if (isEmpty()) {
throw new NoSuchElementException("优先队列为空");
}
Key max = pq[1];
// 第一个和最后一个元素交换
swap(1, N);
// 删除位置N的元素，长度减1
pq[N--] = null;
// 删除后要恢复堆有序状态
sink(1);
if (N > 0 && N == pq.length / 4) {
resize(pq.length / 2);
}
return max;
}
private void swim(int k) {
// k = 1说明当前元素浮到了根结点，它没有父结点可以比较，也不能上浮了，所以k <= 1时候推出循环
while (k > 1 && greater(k / 2, k)) {
swap(k / 2, k);
// 上浮后，成为父结点，所以下标变成原父结点
k = k / 2;
}
}
private void sink(int k) {
// 父结点的位置k最大值为 N/2,若k有左子结点无右子结点，那么2k = N；若两个子结点都有，那么2k + 1 = N
// 有可能位置k只有左子结点，依然要比较，用2k + 1 <= N这个的条件不会执行比较，所以用2k <= N条件
while (2 * k <= N) {
int j = 2 * k;
// 可以取j = N -1,greater(N -1, N);由于下标从1开始，所以pq[N]是有元素的
if (j < N && greater(j, j + 1)) {
// 右子结点比左子结点大 ，取右子结点的下标
j++;
}
// 左子结点或者右子结点和父结点比较
// 如果pq[k] >= pq[j]，即父结点大于等于较大子结点时，停止下沉
if (!greater(k, j)) {
break;
}
// 否则交换
swap(k, j);
// 下沉后，下标变成与之交换的元素下标
k = j;
}
}
private boolean greater(int i, int j) {
return pq[i].compareTo(pq[j]) > 0;
}
private void swap(int i, int j) {
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
public static void main(String[] args) {
MinPQ<Integer> minPQ = new MinPQ<>(4, 3, 1, 2, 5);
System.out.println(minPQ.delMin()); // 1
System.out.println(minPQ.delMin()); // 2
System.out.println(minPQ.delMin()); // 3
System.out.println("还剩" + minPQ.size() + "个"); // 2
System.out.println("当前队列最小元素：" + minPQ.min()); // 4
}
}
堆排序
用优先队列实现排序相当简单，一个比较容易想到的思路是：不断删除最小元素，并按顺序填入原数组。如下
public static void main(String[] args) {
Integer[] a = {4, 3, 1, 2, 5};
MinPQ<Integer> minPQ = new MinPQ<>(a);
for (int i = 0; i < a.length; i++) {
a[i] = minPQ.delMin();
}
System.out.println(Arrays.toString(a)); // [1, 2, 3 ,4, 5]
}
这种做法当然可以，但是需要创建MinPQ对象，引入了额外的空间，可不可以原地排序呢？
我们注意到，上面为MaxPQ写过一个构造方法，传入一个数组，就能构造成有序的堆，其实里面只用到了sink方法！所以我们完全可以将sink方法提取出来，改成静态方法。用基于大顶堆的优先队列，不断将堆顶的最大元素和数组最后一个元素交换，然后对换到堆顶的元素下沉，如此反复，最大元素都按顺序移动到了数组右边，当倒数第二个元素的位置排定后，整个数组也就有序了。
package Chap9;
public class HeapSort {
public static void sort(Comparable[] a) {
// 堆的构造
int N= a.length;
for (int k = N / 2; k >= 1; k--) {
sink(a, k, N);
}
// 最大元素交换到数组右边
// 倒数第二个元素排定数组就已经有序了，所以N = 1时只剩一个元素不用再操作了
while (N > 1) {
swap(a, 1, N--);
sink(a, 1, N);
}
}
private static void sink(Comparable[] a, int k, int N) {
// 父结点的位置k最大值为 N/2,若k有左子结点无右子结点，那么2k = N；若两个子结点都有，那么2k + 1 = N
// 有可能位置k只有左子结点，依然要比较，用2k + 1 <= N这个的条件不会执行比较，所以用2k <= N条件
while (2 * k <= N) {
int j = 2 * k;
// 可以取j = N -1,less(N -1, N);由于下标从1开始，所以pq[N]是有元素的
if (j < N && less(a, j,j+1)) {
// 右子结点比左子结点大 ，取右子结点的下标
j++;
}
// 左子结点或者右子结点和父结点比较
// 如果pq[k] >= pq[j]，即父结点大于等于较大子结点时，停止下沉
if (!less(a, k, j)) {
break;
}
// 否则交换
swap(a, k, j);
// 下沉后，下标变成与之交换的元素下标
k = j;
}
}
// 由于sort方法和sink方法都是从下标1开始算，即认为有元素的区间为[1, a.length]，但实际上传入的数组有元素区间为[0, a.length -1]
// 所以swap(a, p, q)实际交换的元素是a[p-1]和a[q -1]
private static void swap(Comparable[] a, int p, int q) {
Comparable temp = a[p-1];
a[p-1] = a[q-1];
a[q-1] = temp;
}
// // 由于sort方法和sink方法都是从下标1开始算，即认为有元素的区间为[1, a.length]，但实际上传入的数组有元素区间为[0, a.length -1]
// 所以less(a, i, j)实际比较的元素的是a[i-1]和a[j -1]
private static boolean less(Comparable[] a, int i, int j) {
return a[i-1].compareTo(a[j-1]) < 0;
}
// less方法变了，这个方法也得假定处理的区间是[1, a.length]
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a, i + 1, i)) {
return false;
}
}
return true;
}
public static String toString(Comparable[] a) {
if (a.length == 0) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < a.length; i++) {
sb.append(a[i]);
if (i == a.length - 1) {
return sb.append("]").toString();
} else {
sb.append(", ");
}
}
return sb.toString();
}
public static void main(String[] args) {
Integer[] a = {9, 1, 5, 8, 3, 7, 4, 6, 2};
HeapSort.sort(a);
System.out.println(HeapSort.toString(a));
System.out.println(HeapSort.isSorted(a));
}
}
一定要注意一点：sink方法直接沿用了上面优先队列的sink的实现，而优先队列数组第一个位置a[0]是没有使用的！sink方法认为数组有元素的区间是[1, a.length]，但实际上数组a的有元素区间是[0, a.length - 1]，因此所有比较和交换方法中下标都要减小1后再操作。比如sink方法中，swap(a, 2, 4)，sink认为是交换了第2个和第4个元素（a[0]没有使用所以分别对应a[2]、a[4]），但我们传入的是普通数组，下标是从0开始算的，所以实际交换的是a[1]和a[3]才对。
搞清楚了这个关系后，为了减少代码改动，其实只需要在less和swap的内部，下标减1即可，传入的参数还是不变（给sink方法看的），但实际上内部比较的又是它们前面一位元素了。
下面是一个堆排序的轨迹图，最左边一列是对任意顺序的数组进行堆的构造，堆有序后不通过下沉操作对数组排序。
下图结合着上图看，加深理解。下图中标红的元素对应着上面阴影部分中的下沉轨迹。红色的元素参与了比较且被交换，黑色的元素参与了比较但没有被交换，灰色的元素没有参与比较。
堆排序总是将堆顶元素和数组末端元素交换，即使这两个元素相等。在这种情况下，等值元素的相对位置一般发生了变化。所以堆排序是不稳定的排序算法。
堆排序的时间复杂度为O(Nlg N)，下表将各个排序算法的性能都做了比较。
by @sunhaiyu
2017.11.1
