堆排序以及最大优先队列

堆排序（heapsort）是一种比较快速的排序方式，它的时间复杂度为 $O(n\lg n)$，而且堆排序具有「空间原址性」：即任何时候只需要有限（常数个）的空间来存储临时数据。堆排序还被应用在构造优先级队列中。本文将用 Java 实现一个最大堆，并利用它实现优先级队列。

最大堆的性质

1. 是一棵近似的完全二叉树，除了最底层，其它是全满，且从左向右填充。
2. 树的每个节点对应数组一个元素，根节点对应数组下标0元素。
3. 对于下标i，它的父节点下标为(i + 1) / 2 - 1，左孩子节点下标为i * 2 + 1，右孩子节点下标为i * 2 + 2。
4. 最大堆中，每个结点都必须大于等于左右孩子节点。

下面两张图是同一个最大堆：先是二叉树的形式，再是它在数组中的存放方式。

堆排序

堆排序分三步：维护最大堆、建立最大堆，最后反复取出堆顶完成排序。

1. 维护最大堆

为了建立一个最大堆，我们需要设计一个算法来维护最大堆的性质。对于节点i，我们假设它们的左右子树都是最大堆，而节点i因为小于左右孩子而违背了最大堆的性质，因此我们需要对节点i进行逐级下降，从而使得以节点i为根结点的子树满足最大堆的性质。

maxHeapify 的实现如下：

private void maxHeapify(int[] a, int i, int length) {
    int l = left(i);
    int r = right(i);
    int max;
    if (l < length && a[l] > a[i]) {
        max = l;
    } else {
        max = i;
    }
    if (r < length && a[r] > a[max]) {
        max = r;
    }
    if (max != i) {
        swap(a, i, max);
        maxHeapify(a, max, length);
    }
}

上述代码的解释是：对于节点i（即数组下标i），首先获取它的左右子孩子下标，分别存储到l，r变量中，其中left和right函数可以根据最大堆的性质得到，如下：

private int left(int i) {
    return i * 2 + 1;
}

private int right(int i) {
    return i * 2 + 2;
}

变量length是要维护的数组的长度，它的值<=数组的真实长度。临时变量max用来存储节点i，左孩子和右孩子这三者最大者的下标。

因此，首先比较左孩子a[l]是否大于节点i，是的话将左孩子下标l赋值给max，否则，当前最大者仍为节点i，并把i的值赋给max。然后当前最大者和右孩子比较，小于右孩子的话就把下标r赋值给max。

到目前为止，我们找到了节点i，左孩子和右孩子这三者之中的最大者的下标max。如果节点i本来就是最大的，那么就不需要维护了，所以函数结束。否则的话，有孩子节点大于节点i，因此我们需要将节点i和较大的那个孩子进行交换，即swap(a, i, max)，swap函数如下：

private void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

交换之后，节点max的值变成了较小的原来节点i的值，因此，以节点max为根节点的子树可能违背最大堆的性质。注意到此时问题和一开始一模一样，只是节点i变成了节点max，因此递归调用maxHeapify(a, max, length)即可。

如果把第一张图的节点1的值改为1，这时从节点1开始调用maxHeapify(a, 1, a.length)，整个流程如下：

可以看到，经过两次递归调用逐级下沉，原来因为1节点变小，而被打破的最大堆，又重新维护完成。

2. 建立最大堆

我们采用自底向上的方法来建立一个最大堆。通过观察发现，下标为a.length / 2到a.length - 1的节点均为叶子节点，没有子孩子。这意味着，它们已经是一个最大堆，只是仅有一个元素。因此，我们只需要自底向上，对其他节点调用maxHeapify来维护最大堆即可：

private void buildMaxHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        maxHeapify(a, i, a.length);
    }
}

注意，循环变量从a.length / 2 - 1开始，它是最后一个非叶子节点：因为a.length / 2到a.length - 1的节点满足最大堆，所以a.length / 2 - 1的左右子孩子（如果有的话）都是最大堆，符合使用maxHeapify的调用条件。之后下标越来越小，每个节点的孩子都已经在之前被处理过。如果我们对数组[10, 8, 11, 8, 14, 9, 4, 1, 17]进行建立最大堆，那么输出数组为[17, 14, 11, 8, 10, 9, 4, 1, 8]：

3. 堆排序

在第二步建立完成最大堆之后，注意到整个数组的最大元素总是在最大堆的第一个，即a[0]。这时，如果我们拿走第一个元素，放到数组的最后一个位置，然后对第一个元素进行维护最大堆maxHeapify，如此循环进行，便可完成整个数组的排序。对应的实现是：

public void heapSort(int[] a) {
    buildMaxHeap(a);//首先建立最大堆，完成后第一个元素为最大值
    int length = a.length;
    for (int i = a.length - 1; i >= 1; i--) {
        swap(a, i, 0);//将第一个最大的元素移到后面，并且在 maxHeapify 的过程中通过减小 length 忽略它
        length--;
        maxHeapify(a, 0, length);
    }
}

这样我们就完成了对数组的从小到大排序。建堆需要 $O(n)$ 时间，之后 $n-1$ 次 maxHeapify 每次 $O(\lg n)$，总时间为 $O(n\lg n)$。下面用上文的数组把建堆和排序两个阶段完整走一遍，也可以换成随机数组：

堆排序逐步演示

初始堆大小 9 · 第 1 / 44 步

初始数组，还不满足最大堆性质。a[4..8] 都是叶子，建堆从最后一个非叶子节点 a[3] 开始，自底向上。

↺重置‹上一步▶播放下一步›随机数组

速度

1×

进度

• 正在下沉
• 比较的孩子
• 三者最大
• 已排序

最大优先队列

堆排序是一个优秀的算法，在操作系统中可以利用最大堆实现最大优先队列来实现共享计算机系统的作业调度。最大优先队列记录各个作业之间的相对优先级，当某个作业中断后选出具有最高优先级的作业来执行。最大优先级队列应该支持如下操作：

1. maximum()：返回堆的最大值。
2. extractMax()：返回堆的最大值并从堆中删除。
3. heapIncreaseKey(i, key)：将下标为i的元素增大为key。
4. maxHeapInsert(key)：将元素key插入到堆中。

下面依次实现这几个操作。maximum()最简单，直接返回第一个元素：

public int maximum() {
    return a[0];
}

extractMax也很简单，取出第一个后，只需把最后一个元素放到第一个，然后对第一个元素进行维护最大堆即可：

public int extractMax() {
    int max = a[0];
    a[0] = a[a.length - 1];
    int[] newA = new int[a.length - 1];
    System.arraycopy(a, 0, newA, 0, newA.length);
    a = newA;
    maxHeapify(a, 0, a.length);
    return max;
}

heapIncreaseKey(i, key)会增大下标为i的元素为key。首先将a[i]的值更新为key，因为增大的a[i]关键字可能会违背最大堆的性质，因此我们需要对a[i]进行逐级上升。即将当前元素逐级与父节点比较，如果大于父节点，则与父节点进行交换，一直到当前元素小于父节点为止：

public void heapIncreaseKey(int i, int key) {
    if (key > a[i]) {
        a[i] = key;
        while (i > 0 && a[parent(i)] < a[i]) {  //逐级上升
            swap(a, parent(i), i);
            i = parent(i);
        }
    } else {
        throw new IllegalArgumentException("key is too small");
    }
}

private int parent(int i) {
    return (i + 1) / 2 - 1;
}

maxHeapInsert(key)十分简单，因为它等价于数组长度增加一，然后最后一个元素设置为-∞，然后把它增大为key的操作：

public void maxHeapInsert(int key) {
    int[] newA = new int[a.length + 1];
    System.arraycopy(a, 0, newA, 0, a.length);
    newA[newA.length - 1] = Integer.MIN_VALUE;
    this.a = newA;
    heapIncreaseKey(a.length - 1, key);
}

在一个包含 $n$ 个元素的堆中，所有优先级队列的操作都可以在 $O(\lg n)$ 的时间内完成。实际工程中一般直接使用标准库：Java 的 java.util.PriorityQueue 就是基于二叉堆实现的，默认是最小堆，传入 Comparator.reverseOrder() 即可得到最大堆。

源代码可以在这里找到：lufficc/Algorithm

文章来自自己的理解以及算法导论。