列表中的树
二叉堆是一棵不需要指针的树。位置 0 是根节点,位置 i 的子节点是位置 2i + 1 和 2i + 2,所以位置 1 和 2 是根节点的子节点,位置 3 到 6 是下一层,以此类推。除最后一层外,每层都是满的,最后一层从左往右填。在最大堆中,每个父节点都不小于它的子节点,所以最大值总在根节点。
下沉
所有工作都由一种操作完成。要把一个值下沉,就把它与子节点比较。如果较大的子节点比它大,两者交换,然后再与新的子节点比较。当没有子节点比它大,或者到达底部时就停止。由于树只有约 log₂ n 层,一次下沉最多约 2 log₂ n 次比较。
先建堆,再排序
建堆时,从最后一个父节点往回到根节点,依次把每个父节点下沉。每个父节点下沉之前,它下面的子树都已经是堆。然后排序:把根节点,即最大值,与堆的最后一个值交换。这个值就到了最终位置。堆缩短一个,落到根节点的值下沉以修复堆。重复直到只剩一个值。
示例
以 5, 1, 4, 2, 8 为例。建堆时,1 下沉到 8 之下,然后 5 下沉到 8 之下,得到 8, 5, 4, 2, 1。现在 8 交换到末尾;1 落到根节点,越过 5 和 2 下沉:5, 2, 4, 1 | 8。然后 5 移到末尾,1 越过 4 下沉:4, 2, 1 | 5, 8。再经过两轮,列表排好:1, 2, 4, 5, 8,共 12 次比较、10 次交换。
优点和缺点
即使在最坏情况下,堆排序的时间也与 n log n 成正比,而且不需要额外内存。快速排序可能慢到 n²,归并排序需要和列表一样长的缓冲区,所以堆排序是稳妥的后备:C++ 标准库使用的 introsort 在快速排序的分区出问题时就改用它。在真实的计算机上,它通常比两者都慢,因为它在列表中相距很远的位置之间跳跃,而且它不稳定。J. W. J. Williams 于 1964 年发表了堆排序,同时提出了二叉堆。
动手探索
打开应用,按“单步”。柱子上方的树显示堆:正在下沉的值有自己的颜色,与它比较的子节点会高亮,每次交换都会同时显示在树和柱子上。堆建好后,看根节点交换到末尾,变成绿色,并离开这棵树。
常见问题
堆排序的时间复杂度是多少?
最好、平均和最坏情况下都是 O(n log n)。建堆需要 O(n),n − 1 次取出每次需要 O(log n)。它是原地排序,只需 O(1) 的额外内存。
堆排序和选择排序有什么区别?
两者都一次次取出剩余值中最大(或最小)的那个。选择排序通过完整扫描未排序部分来找它,每次 n 次比较。堆排序把未排序部分放在堆里,最大值已经在顶端,修复堆只需约 log n 次比较。
除了排序,堆还有什么用?
优先队列:堆能立即给出最大(或最小)的元素,并能在约 log n 步内添加或删除元素。调度器、Dijkstra 最短路径算法和事件模拟都会用到它。
堆排序稳定吗?
不稳定。把根节点交换到末尾会让值移动很远,所以相等的值可能改变彼此的顺序。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试堆排序