「优先队列」专题 2：堆排序、heapify、原地堆排序

「队列」专题 2：堆排序、heapify、原地堆排序

说明：

以下出现 sift down 的地方有可能写作 shift down，还有可能写作 sink ，它们都表示「下沉」的意思；

同理，出现 sift up 的地方有可能写作 shift up，还有可能写作 swim ，它们都表示「上浮」的意思；

因为我个人的原因，给大家造成不便，请各位谅解。

以下说明来自 liuyubobobo 对于问题：《请问到底是sift down 还是shift down》 的回复，我做了删改。

补充说明：对于命名：推荐用 sift。 参见 wiki 百科：https://en.wikipedia.org/wiki/Binary_heap 。

由于 sift 和 shift 拼写很接近，取 shift 的意思，没什么不妥的（甚至更贴切），所以很多资料也是使用 shift。在理解上，不会有歧义。或许是为了消除这个歧义，很多教材，会避免使用 sift/shift 的用法。比如大名鼎鼎的《算法（第 4 版）》，使用的是 swim（上浮）和 sink（下沉）：https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MaxPQ.java.html 。

补充一下，之所以使用 shift 大家觉得没问题，是因为在解释这个操作的时候，一般都会用到 shift 这个词，顺便说一下，《算法导论》也避免了使用 sift/shift 的问题。但是《算法导论》取的名字非常不好，我个人不建议使用，比如用 max-heapify 表示下沉，完全没有体现出下沉这个动作。

结论：如果你对此特别在意，请使用 sift ，这应该是原始论文所用的名称；但其实，无所谓，完全不影响交流，也不会有人笑话你的。：）

基础堆排序和 Heapify

这一节我们介绍两个使用堆或者说基于堆的思想进行排序的算法。

思路 1 ：一个一个地往最大堆里面放元素，然后再一个一个地取出，倒序放置于一个空数组中，就完成了元素的排序；

思路 2 ：一次性把整个数组复制到一个新数组，通过新数组 heapify 操作，使得新数组成为一个最大堆，然后再一个一个地取出，倒序放置于一个空数组中，就完成了元素的排序。

思路 1：一个一个放进最大堆，再一个一个地取出完成排序

我们首先要明确的是，堆排序的时间复杂度是 $O(n \log n)$。

我们可以从以下几个维度进行不同算法性能的比较，对数量级是 100 万个元素的数组进行排序。

使用的排序算法维度：归并排序，快速排序，三路快速排序，堆排序（借助额外空间的堆排序）。

元素特点维度：1、随机；2、几乎有序；3、含有大量相同元素的数组。

Java 代码：

public class HeapSort1 implements ISortAlgorithm {
    @Override
    public String getName() {
        return "第 1 个版本的堆排序算法";
    }

    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        MaxHeap maxHeap = new MaxHeap(length);
        for (int i = 0; i < length; i++) {
            maxHeap.insert(arr[i]);
        }
        for (int i = length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }
}

我们在上一小节，介绍了将一个元素 insert 到最大堆中，和从最大堆中取出一个元素，仅仅通过这两个操作，就可以完成排序任务。方法很简单，把待排序数组中的元素全部 insert 到最大堆里，然后再一个一个取出来，因为我们要按照升序排序，因此从后向前放置从最大堆中拿出的元素。

这个方法有一个缺点，那就是要使用和数组元素个数相等的最大堆空间，即空间复杂度是 $O(n)$。

而这一节我们要介绍的是一种直接使用堆的 sift down 方法完成排序任务的方法，这种方法使用 $O(1)$ 的空间复杂度，用于一个临时表变量的存储。

首先，我们介绍一个操作，名为 heapify 。

思路 2 ：一次性复制数组元素到新的数组，新数组自我调整成最大堆

什么是 Heapify？

Heapify 是尝试将一整个数组构建成一个堆的方式，即通过调整自己，交换数组中的元素，就可以把自己整理成一个最大堆。

理解 Heapify 关键的部分

• 所有的叶子结点就是一个最大堆，此时每个堆中的元素只有 1 个；
• 当我们的使用的数组从下标 1 开始计数的前提下，第 1 个非叶子的结点的下标是 index / 2（自己画一个图，就可以看清楚这个规律，可以使用数学归纳法来证明），如何让它满足堆的性质呢？ sift down 就可以了。
• 思考：我们为什么不用 sift up ？
  我的思考如下：如果使用 sift up 的话，那就得将数组中所有的元素都 sift up，相比于只用一半的元素 sift down 而言，工作量会少很多。
• 从 index / 2 递减到根（index==1的时候）依次去完成 sift down，一开始就排除了 len / 2 这么多元素。

heapify

使得一个数组是堆有序的操作就叫做 heapify 。具体的做法是：从最后一个非叶子结点开始到下标为 $0$ 的位置，逐个 sift down。

在上一步「堆排序」中，我们注意到，有这样一个操作：把待排序数组按顺序放入一个堆（入队），这一步得一个接着一个按照顺序放入堆中，实际上，可以通过一个称之为 heapify 的操作，让这个数组自行调整成一个最大堆，即使之「堆有序」，而此时无需借助 $O(n)$ 空间就完成了最大堆的构建。事实上，只需对数组中一半的元素执行 sift down 就可以了。

以下代码还是使用了 $O(n)$ 空间，主要是为了说明 heapify 。

heapify 如下所示：从下标的 self.count // 2 位置开始，直到索引为 $0$ 的元素结束，逐个下沉，就可以让一个数组堆有序。

说明：下标为 self.count // 2 位置是从下到上第 1 个非叶子结点的下标。

Java 代码：

/**
 * 传递一个数组，形成一个最大堆
 * 理解 heapify 是关键
 *
 * @param arr 待排序的数组元素
 */
public MaxHeap(int[] arr) {
    int length = arr.length;
    data = new int[length + 1];
    for (int i = 0; i < length; i++) {
        data[i + 1] = arr[i];
    }
    // 添加一个元素，就要把 count 加 1 ，因为我们是一次性添加，所以就直接将 count 赋值为 length 就可以了
    // 这一步赋值千万别忘了
    count = length;
    // 理解这一步是关键 heapify
    for (int i = length / 2; i >= 1; i--) {
        siftDown(i);
    }
}

Python 代码：

class MaxHeap:
    def __init__(self, nums):
        self.capacity = len(nums)
        self.data = [None] * (self.capacity + 1)
        self.count = len(nums)
        self.__heapify(nums)

    def __heapify(self, nums):
        # 挨个赋值
        for i in range(self.capacity):
            self.data[i + 1] = nums[i]
        for i in range(self.count // 2, 0, -1):
            self.__sift_down(i)

这样，我们就可以写出我们的第 2 个使用堆排序的算法了，直接把数组传到最大堆这个数据结构里面。

heapify 以后挨个取出来，倒着放回去，也可以完成排序，就不用一个一个放进去，做上浮的操作了。整体上排序会比一个一个放进去快一些。

Java 代码：通过 heapify 将数组重组成最大堆实现的排序

public class HeapSort2 implements ISortAlgorithm {
    @Override
    public String getName() {
        return "第 2 个版本的堆排序算法";
    }

    @Override
    public void sort(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        int length = arr.length;
        for (int i = length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }
}

重要结论：堆排序在整体上的性能不如归并排序和快速排序。但是，堆这种数据结构更多的时候用于动态数据的维护。

一个数学结论：将 $n$ 个元素逐一插入到一个空堆中，时间复杂度是 $O(n \log n)$。 heapify 的过程，时间复杂度是 $O(n)$。

HeapSort2 会快一点的原因是：一上来我们从 n / 2 这个地方开始，逐一操作，排除了 n/2 个元素，所以效率肯定比第 1 种好。

可是这两种基于堆的排序算法，我们在堆排序的过程中，使用了额外的空间（即 MaxHeap 中的数组），使用了 $O(n)$ 的空间复杂度。那么不借助额外的空间是不是也可以完成堆排序呢？这就是我们下一节要介绍的内容——原地堆排序。

原地堆排序

通过上一节的学习，我们知道一个数组通过 heapify 操作，即通过一半的元素执行 sift down 的操作可以逐渐地整理成一个最大堆。

我们把「原地堆排序」拆解为以下 3 个部分：

1、首先，转换思维，堆从数组下标 $0$ 开始编号；

代码很多地方都要改，好在并不复杂，正好可以帮助我们复习堆的 sift down 操作，如果只是用于排序任务，不需要 sift up 操作；

2、 sift down 操作要设计成如下的样子，设计一个表示 end 的变量，表示待排序数组的 [0, end]（注意是闭区间）范围是堆有序的。

上一节我们将一个数组通过 heapify 的方式逐渐地整理成一个最大堆。而原地堆排序的思想是非常直观的，从 sift down 的操作我们就可以得到启发，堆中最大的那个元素在数组的 0 号索引位置，我们把它与此时数组中的最后一个元素交换，那么数组中最大的元素就放在了数组的末尾，此时再对数组的第一个元素执行 sift down ，那么 sift down 操作都执行完以后，数组的第 1 个元素就存放了当前数组中的第 2 大的元素。依次这样做下去，就可以将一个数组进行排序。

理解这个原理的关键之处：对堆顶元素执行了 sift down 操作以后，就会把这个堆中的最大的元素挪到堆顶。

此时，因为用到了下标，并且须要用到下标为 $0$ 的数组元素，因此我们就要将最大堆中数组的下标从 $0$ 开始计算，重新写一套堆的 API。

我们整理一下，其实这个思想跟「选择排序」是一样的，只不过我们每一轮选出一个当前未排定的数中最大的那个，即：「选择排序」 + 「堆」 就是「堆排序」。

「堆排序」代码实现的注意事项：

1、此时最大堆中数组的下标从 $0$ 开始计算。与之前下标从 $1$ 开始的最大堆实现比较，性质就发生了变化，但并不会不好找，我们可以自己在纸上画一个完全二叉树就可以很清晰地发现规律：

• ${\rm parent}(i)=\cfrac{i-1}{2}$；
• ${\rm left \quad child}(i) = 2 \times i +1$；
• ${\rm right \quad child}(i) = 2 \times i +2$；
• 最后一个非叶子结点的索引是：$\cfrac{count-1}{2}$；

2、原地堆排序，因为下标从 $0$ 号开始，相应的一些性质在索引上都发生变化了；

3、注意到我们只有 sift down 的操作，对于 sift down 的实现，一些细节就要很小心， sift down 是在一个区间内进行的，我们在设计新的 sift down 方法的实现的时候，应该设计待排序数组区间的右端点。

Java 代码：

/**
 * 原地堆排序
 * Created by liwei on 17/5/15.
 */
public class HeapSort3 implements ISortAlgorithm {
    @Override
    public String getName() {
        return "原地堆排序";
    }


    /**
     * 原地堆排序的目标就是，不再借助 MaxHeap 这个数据结构进行排序，减少了空间复杂度
     * 注意：此时我们的数组索引从 0 开始定义(自己在纸上画一下图，就能清晰地明白算法实现的含义)
     *
     * @param arr 待排序数组
     */
    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        // 将一个无序的数组组成了一个最大堆，第 1 个元素就是最大值
        for (int i = (length - 1) / 2; i >= 0; i--) {
            siftDown(arr, length, i);
        }

        // 代码逻辑非常简单明确，完全可以自己写出来
        for (int i = length - 1; i > 0; i--) {
            swap(arr, 0, i);
            siftDown(arr, i, 0);
        }
    }


    /**
     * 从索引为 0 开始，up 为止 [0,up] 的数组元素进行 shift down 的操作
     *
     * @param arr 
     * @param up 这里的 up 定义为形成堆这个数据结构的最大下标（从索引 0 就放元素），
     *           即在区间 [0,up] 范围内 Shift Down
     * @param index 对索引是 index 的元素执行 Shift Down 操作
     */
    private void siftDown(int[] arr, int up, int index) {
        // 如果有右孩子的结点，并且右孩子结点比左孩子结点的值要大
        // 此时可以忽略左孩子结点的存在，拿右孩子结点的数值和自己比较

        // 只要它有左孩子，就不是叶子结点，就可能 shift down，注意：这里是小于号
        while (2 * index + 1 < up) {
            int j = 2 * index + 1;
            if (j + 1 < up && arr[j] < arr[j + 1]) {
                j = j + 1;
            }
            if (arr[index] < arr[j]) {
                swap(arr, index, j);
                index = j; // 留意
            } else {
                break;
            }
        }
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

}

Python 代码：

def __sift_down(nums, end, k):
    # end ：数组 nums 的尾索引，
    # __sink 方法维持 nums[0:end]，包括 nums[end] 在内堆有序
    assert k <= end
    temp = nums[k]
    while 2 * k + 1 <= end:
        # 只要有孩子结点：有左孩子，就要孩子结点
        t = 2 * k + 1
        if t + 1 <= end and nums[t] < nums[t + 1]:
            # 如果有右边的结点，并且右结点还比左结点大
            t += 1
        if nums[t] <= temp:
            break
        nums[k] = nums[t]
        k = t
    nums[k] = temp


def __heapy(nums):
    l = len(nums)
    for i in range((l - 1) // 2, -1, -1):
        __sift_down(nums, l - 1, i)


def heap_sort(nums):
    l = len(nums)
    __heapy(nums)

    for i in range(l - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        __sift_down(nums, i - 1, 0)

说明：首先进行一次 heapify 的过程：从索引为 $\cfrac{count-1}{2}$ 的结点开始执行 shift down。heapify 过程的代码框架几乎是套路，一定要熟悉，只不过我们要弄清楚，我们的最大堆是从索引为 $0$ 的位置开始存放元素，还是从索引为 $1$ 的地方开始存放元素。

// 将一个无序的数组组成了一个最大堆，第 1 个元素就是最大值
for (int i = (length - 1) / 2; i >= 0; i--) {
    siftDown(arr, length, i);
}

到此为止，堆的排序算法就已经介绍完了，下面我们对之前学习过的排序算法作一个总结。

排序算法总结

平均时间复杂度

时间复杂度分为平均时间复杂度、最好时间复杂度和最坏时间复杂度。对于一个算法来说，往往有很多特殊情况，一般而言，我们所说的时间复杂度都指最坏时间复杂度。

对我们学习过的各种排序算法的总结和对比

快速排序相对会更快一些。一般系统级别的排序，是用快速实现的。如果有大量重复键值，可以使用三路快排。

排序算法的稳定性

查资料了解什么是排序算法的稳定性。可以通过自定义比较函数，让排序算法不存在稳定性问题。系统级别的排序算法，如果要求稳定性的话，一般使用归并排序。

对未来的探索

是不是存在一种神秘的排序算法？让所有指标达到最优呢。liuyubobobo 老师告诉我们，目前还没有。

本文源代码

• Java：代码文件夹；
• Python：代码文件夹。

（本节完）