企业官网建设流程全解析

提到“堆排序（Heap sort）”，很多人第一反应是：又一个要背的排序算法。但我在实际工作里见过太多人把“排序”和“维护优先级”混为一谈，才意识到这个算法背后的思想，比算法本身值钱得多。

有次我帮一个同事看线上问题，他写了个任务调度逻辑，任务列表几百个，每个任务带优先级。他的做法是：每执行完一个任务，就把整个列表按优先级重新排一遍，然后取第一个。听上去没毛病，对吧？但你想，执行完一个任务之后，剩下的几百个任务之间的相对顺序根本没有变，你只需要拿到当前最大的那一个。一次全排序是 O(n log n)，而用堆的话，取最大元素和重新调整都只需要 O(log n)。这个差距在数据量上来之后非常明显。所以他需要的不是“把数组变成有序序列”，而是“维护一个能快速取出最大元素的集合”。这就是堆的本质，也是堆排序能成为经典算法的原因。

这篇文章我会从堆排序的底层数据结构讲起，把建堆、排序、复杂度这些环节一块块拆开，最后再聊几个实际写代码时容易踩的坑。不管你是准备面试想现场手写堆排序，还是在读源码的时候碰到优先队列的实现，又或者只是想搞清楚为什么很多语言的内置排序算法不是堆排序，这篇应该都能帮到你。

1. 堆排序解决的是哪一类问题

1.1 从一次代码评审中的“反复排序”说起

先说开头那个任务调度的例子。同事的原始代码大概长这样：

tasks = [ {"priority": 3, "name": "A"}, {"priority": 8, "name": "B"}, {"priority": 1, "name": "C"}, # ... ] while tasks: tasks.sort(key=lambda x: x["priority"], reverse=True) task = tasks.pop(0) execute(task)

这段代码的问题很明显：每执行一个任务就做一次全量排序。假设任务有 1000 个，第一次排序 O(n log n)，之后每次都把剩下的数据重新排一遍。如果任务执行过程还有新任务进来，那每次插入也是一次全排序的代价。

正确的思路是：任务之间的相对顺序不重要，重要的只有“下一个该执行谁”。这时候一个二叉堆就够了——插入 O(log n)，取出最大值 O(log n)，并且不需要任何额外的全量排序。

我后来把代码改成了用堆实现的任务调度器，核心逻辑是：

import heapq from dataclasses import dataclass @dataclass(order=True) class Task: priority: int name: str = "" tasks_heap = [] heapq.heappush(tasks_heap, Task(3, "A")) heapq.heappush(tasks_heap, Task(8, "B")) heapq.heappush(tasks_heap, Task(1, "C")) while tasks_heap: task = heapq.heappop(tasks_heap) execute(task)

同样的 effect，维护成本完全不同。这个场景告诉我们：堆排序不只是“给一个数组排序”的算法，它更是一种组织数据的方式。理解堆排序，本质上就是在理解“动态集合中的最大/最小值维护”这个更底层的问题。

1.2 堆排序与其他排序算法的分工

既然聊排序，就得说清楚一件事：堆排序不是一个“比快排更强”的算法，它们是不同场景下的不同选择。

看下面这张表：

堆排序独有的优势是什么？它是“最坏也有 O(n log n) + 原地排序 O(1) 空间”的算法。快速排序大多数时候表现很好，但一旦遇到不合理的基准点选择，最坏会退化到 O(n²)。归并排序虽然稳定且复杂度有保证，但需要额外 O(n) 的辅助空间。堆排序在这两点上是刚的：不管输入数据长什么样，时间复杂度稳稳的 O(n log n)，空间只要放原数组的那点内存。

这也是为什么很多标准库里的排序在特定条件下会切换到堆排序。最典型的就是“内省排序”：先走快排，如果递归深度异常了，立刻转成堆排序来兜底，保证整体不退化。所以堆排序不是被时代淘汰的算法，它是快排背后那个兜底的保险丝。

1.3 堆排序适合什么场景

说结论吧，我理解的合适场景有这几个：

• 需要“最坏情况也有保证”的排序，且空间要求苛刻：比如在某些嵌入式环境、内存受限但数据规模固定的排序任务。
• 作为算法面试的基础功：手写堆排序几乎是考察“递归分治 + 抽象数据结构 + 下标操作”的综合题。
• 理解更复杂的堆应用：Top K 问题、优先队列、定时器、图算法里的最小堆等等。这些应用真正流行的原因，是因为堆能在“动态插入”和“取极值”之间保持平衡，这是任何一次全排序都做不到的。

至于平常业务代码里给一个数组排序，真的用内置sort就够了。没必要自己造轮子。但了解堆排序的原理，是你能“正确使用和不使用”它的前提。

2. 先把二叉堆这个数据结构搞明白

2.1 完全二叉树的数组表示法

堆排序依赖的底层数据结构是二叉堆（Binary Heap）。最直观的理解方式，是把二叉堆看成“一棵完全二叉树，存储在数组里”。

完全二叉树的意思是：除了最后一层，其他每一层都是满的；最后一层的节点从左到右连续排放。正是因为结构是“紧凑”的，所以我们能用数组存放它，而不是像普通二叉树那样用指针。

假设根节点放在数组下标 0 的位置，那么对于任意下标i的节点，它的左右孩子、父节点的下标是固定规律：

• 左孩子下标：2 * i + 1
• 右孩子下标：2 * i + 2
• 父节点下标：(i - 1) // 2

我写过一个直观的例子。数组：

[10, 9, 8, 5, 1, 3, 2, 4]

对应下标关系：

这个映射关系是堆排序所有下标计算的根基。写代码的时候，你其实不是在“操作一棵树”，而是在“操作一维数组”，但脑子里必须随时能把它还原成一棵树。

2.2 最大堆的两条不变式

二叉堆分最大堆和最小堆。堆排序通常用最大堆来排升序。

最大堆要满足两条规则：

1. 它是完全二叉树，数组里没有“空洞”。
2. 对任意节点i，它的值不小于它的左孩子和右孩子的值：arr[i] >= arr[2*i+1]且arr[i] >= arr[2*i+2]（前提是孩子存在）。

由第二条可以推出一个很关键的性质：堆顶（也就是数组的第一个元素）一定是整个数组的最大值。这保证了我们每次“取堆顶”都能拿到当前范围内的最大元素。

最小堆正好相反，父节点小于等于孩子，堆顶是集合中的最小值。

有一点要特别说明：堆不是完全有序数组。它只保证“层级之间有序”——父大子小，但同一层的节点之间谁大谁小完全随意。比如[10, 9, 8, 5, 1, 3, 2, 4]这个堆里，左子树和右子树之间的节点就没有可比性。这恰恰是堆高效的原因：它只维护了一种“局部强弱关系”，维护成本比完全排序低得多。

2.3 为什么堆比“全排序”更适合动态场景

回到任务调度的例子。如果我用一个有序数组来维护任务列表，新增一个任务时，必须把数组中的元素往后挪来腾出位置，最坏要 O(n)；如果用普通排序，每次插入重新全排序，那更糟糕。而二叉堆的新增操作（上浮）和删除堆顶操作（下沉）都只需要 O(log n)。

这就是数据结构“用部分有序换维护效率”的经典思路。堆排序也正是利用这种特性：先构建一个最大堆，然后反复取出堆顶，像挤牙膏一样把元素一个个按从大到小的顺序挤出来，从而实现排序。

3. 建堆阶段：为什么从最后一个非叶子节点开始

3.1 heapify 的标准动作

堆排序里最核心的操作叫heapify（下沉调整）。它的作用是：假设某个节点的左右子树都已经是合法的最大堆，但这个节点本身可能比它的孩子小，那么把它“下沉”到合适的位置，使整棵子树重新成为最大堆。

标准实现如下：

def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)

这段代码的逻辑很简单：

1. 比较大根节点i、左孩子、右孩子三者谁的值最大。
2. 如果最大值不是当前节点，就把它和最大的孩子交换。
3. 交换之后，原来最大的孩子位置现在放的是原来的父节点，它可能仍然比它的新孩子小，所以要递归地继续下沉。

为什么要求左右子树“已经是合法堆”？因为heapify不是一个从零开始建堆的过程，而是一个“修复过程”。它默认的是：问题只出在根节点上，子树内部已经合规。这个前提很关键，后面建堆时我们会利用它。

3.2 自底向上建堆的推导

如果给你一个完全乱的数组，怎么构建一个最大堆？

一个自然的想法是：从数组最后往前，逐个调用heapify。但细想一下，只要子树不是堆，heapify的假设就不成立。所以更合理的顺序是从最后一个非叶子节点开始，往前处理到根节点。

为什么是最后一个非叶子节点？因为再往后的节点全是叶子节点。叶子节点没有孩子，天然满足最大堆的性质（一个节点比“不存在的孩子”大，这当然成立）。所以完全不需要处理它们。

那么最后一个非叶子节点的下标怎么求？对于长度为n的数组，最后一个元素的下标是n-1，它的父节点就是(n-1-1) // 2 = n//2 - 1。所以建堆的循环起点是n // 2 - 1。

代码：

for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i)

从后往前处理，处理到某个节点时，它的左右子树一定已经各自成为合法的堆。因为它的孩子下标更大，已经在前面的循环里处理过了。这样，每个heapify调用的前置条件都成立。

这里有个很容易踩的误区：有人会把建堆循环写成从 0 到 n 正向扫一遍。那样做的话，先处理的上层节点，其下层子树可能还没堆化，heapify的递归调整依然可能把乱序传下去，最终结果往往得不到一个正确的堆。正确的方向永远是自底向上。

3.3 一个完整数组的建堆演示

拿一个比较直观的例子，数组[4, 10, 3, 5, 1, 8, 2, 9]，长度 8，所以n // 2 - 1 = 3。我们从下标 3 开始往前调整。

第一步，处理下标 3 的节点，值为 5。它的左孩子是下标 7，值为 9，右孩子不存在。9 > 5，交换：

[4, 10, 3, 9, 1, 8, 2, 5]

第二步，处理下标 2 的节点，值为 3。左孩子下标 5 值为 8，右孩子下标 6 值为 2。8 最大，交换：

[4, 10, 8, 9, 1, 3, 2, 5]

第三步，处理下标 1 的节点，值为 10。左孩子下标 3 值为 9，右孩子下标 4 值为 1，10 已经最大，不动。

第四步，处理下标 0 的节点，值为 4。左孩子下标 1 值为 10，右孩子下标 2 值为 8。10 最大，交换 4 和 10：

[10, 4, 8, 9, 1, 3, 2, 5]

这里heapify递归继续检查下标 1 的位置。下标 1 现在的值是 4，它的孩子是下标 3 的 9 和下标 4 的 1。9 最大，交换：

[10, 9, 8, 4, 1, 3, 2, 5]

然后继续检查下标 3 的位置，值为 4，它的孩子是下标 7 的 5。5 更大，交换：

[10, 9, 8, 5, 1, 3, 2, 4]

最终，我们得到了一个合法最大堆：[10, 9, 8, 5, 1, 3, 2, 4]。堆顶 10 是最大值，并且每个父节点都不小于它的孩子。这个演示也解释了为什么建堆的时候要“从后往前”：每处理一个节点，它的子树已经是可靠的基础，剩下的问题只是把当前节点“插”到合适位置。

4. 排序阶段：交换堆顶、缩小范围、再下沉

4.1 排序循环里发生的三件事

建堆完成后，最大值在数组的开头。要得到升序数组，还需要一个排序阶段。这个阶段做的事情非常机械：

1. 把堆顶元素和数组当前末尾元素交换。因为堆顶是当前最大值，交换后最大值就“定居”在末尾。
2. 把堆的有效范围缩小一个位置，忽略已经排好的末尾元素。
3. 对新堆顶执行heapify，把剩下的元素重新调整成最大堆。

重复这三步，直到堆的范围只剩一个元素。

这里的关键点是：每次交换完，最大的元素就再也不用动了。堆的有效长度从n缩到n-1、n-2……直到 1。整个数组从后往前逐渐变成有序升序。正因为是在同一个数组里原地操作，堆排序的空间复杂度是 O(1)。

对应代码：

for i in range(n - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0)

注意heapify的第二个参数传的是i，而不是n。它的含义是“当前堆的有效长度”。交换之后，下标i位置的元素已经被永久放置在最终位置，不能再参与调整。

4.2 用手工走一遍关键轮次

继续用上面的堆[10, 9, 8, 5, 1, 3, 2, 4]做演示。

第 1 轮：i=7。交换arr[0]=10和arr[7]=4：

[4, 9, 8, 5, 1, 3, 2, 10]

现在 10 已经归位。对前 7 个元素执行heapify：

• 下标 0 的 4 和左孩子 9、右孩子 8 比，9 最大，交换。
• 继续处理下标 1 的 4，它的孩子是下标 3 的 5 和下标 4 的 1，5 最大，交换。

结果：

[9, 5, 8, 4, 1, 3, 2, 10]

第 2 轮：i=6。交换堆顶 9 和末尾元素 2：

[2, 5, 8, 4, 1, 3, 9, 10]

对前 6 个元素执行heapify：

• 下标 0 的 2 和孩子 5、8 比，8 最大，交换。
• 继续处理下标 2 的 2，它的孩子是下标 5 的 3，3 更大，交换。

结果：

[8, 5, 3, 4, 1, 2, 9, 10]

能看到规律：每轮结束后，数组末尾都会多一个“已经排好的最大值”。继续这个过程到只剩一个元素，整个数组就会变成升序。

4.3 完整的堆排序代码

把上面的建堆和排序阶段合起来，就是一个完整的降序版堆排序？等一下，前面这个版本用的是最大堆，排序结果是升序。完整代码如下：

def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n = len(arr) # 建堆 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 排序 for i in range(n - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0)

如果原数组[4, 10, 3, 5, 1, 8, 2, 9]经过heap_sort，结果会是[1, 2, 3, 4, 5, 8, 9, 10]。

有几个使用细节值得注意：

• heap_sort是原地排序，会直接修改传入的数组。如果你需要保留原数组，调用前先arr.copy()。
• 这个版本的实现用的是最大堆，输出升序。如果你想要降序，可以改用最小堆，或者更简单的方式，在比较上取反逻辑。
• 构建堆的循环起点写成n // 2 - 1是最准确的。写n // 2甚至n // 2 + 1也不会报错，因为那些下标的节点是叶子，heapify会直接返回，只是多做了一些无用功。

5. 堆排序的真实代价：复杂度、稳定性与缓存

5.1 时间复杂度和空间复杂度怎么算出来的

堆排序的时间复杂度有两个部分：建堆阶段和排序阶段。

建堆阶段，很多人凭感觉认为复杂度是 O(n log n)，因为每个节点都要进行调整。但实际上，完整的数学推导结果是 O(n)。直觉是这样的：堆的不同层节点数量不一样。越靠近底层的节点数量越多，但它们下沉的路径短；越靠近顶层的节点数量越少，但它们下沉的路径长。把每一层的调整代价加总，最后会收敛到一个线性复杂度，而不是 n 个节点乘以 log n 的深度。

排序阶段则很简单：每次取堆顶并调整需要 O(log n)，一共取 n-1 次，所以是 O(n log n)。

总复杂度就是 O(n log n)。关键是这个复杂度与输入数据的初始顺序无关。快速排序在最好情况下是 O(n log n)，遇到特定输入可能退化到 O(n²)；归并排序无论什么情况都是 O(n log n)，但要额外 O(n) 空间。堆排序则是“最坏、最好、平均”都是 O(n log n)，且属于原地排序。

空间复杂度方面，不考虑递归调用栈，堆排序只使用常数级额外空间，O(1)。如果算递归深度，heapify的递归深度是树高 O(log n)，但也仅此而已。一般我们把堆排序归类为原地排序算法。

5.2 为什么它不是稳定排序

稳定性指的是：两个相等的元素，排序后能不能保持原来的相对顺序。堆排序是不稳定的。

原因在于堆内部的调整方式和“堆顶与末尾元素交换”的阶段。举个简单例子，数组：

[3a, 3b, 1]

下标 0 是 3a，下标 1 是 3b，下标 2 是 1。建堆阶段，3a 和 3b 相等，heapify中用的是“严格大于”才交换，所以不会交换它们，堆还是[3a, 3b, 1]。

排序阶段，第一轮：交换堆顶 3a 和末尾元素 1：

[1, 3b, 3a]

两个 3 的相对位置反了。原来 3a 在前，现在 3a 跑到了 3b 后面。稳定排序的要求是相等元素排序后仍保持原顺序，这里明显不满足。

这个不稳定性的根源在于：堆排序需要把堆顶元素“甩”到数组末尾，这个操作会跨越中间一堆元素，完全可能改变相等元素的相对顺序。如果你需要稳定排序，堆排序不是一个合适的选择，归并排序是更稳妥的答案。

5.3 缓存不友好：堆排序最容易忽略的短板

看复杂度的表格，堆排序的时间复杂度很优秀，但很多实际测试里它的表现并不如快速排序，原因除了常数项之外，还有一个现代计算机体系结构的问题：缓存命中率。

数组在内存中是连续存储的。快速排序倾向于对整个数组进行分段扫描，访问模式是连续的，能充分发挥 CPU 缓存预取的优势。归并排序虽然需要额外空间，但它读写数组也是相对连续的。

堆排序不一样。它在调整堆的时候，访问的下标是i、2*i+1、2*i+2，父子节点在数组中相隔会越来越大。对于小数组这无所谓，但数据量一大，这种“跳跃式”访问就非常容易造成缓存未命中。这也就是常说的“常数项大”。它隐藏在大 O 复杂度里，实际表现却实实在在地影响运行时间。

这也是为什么语言内置的通用排序算法很少选用纯堆排序的原因。它们往往选择快速排序，再用堆排序兜底最坏情况。

6. 实操心得：写堆排序容易踩的坑

6.1 下标和边界：0-based 下的判断技巧

堆排序的递归实现里，最容易写错的就是边界判断。严格来说，每次都比较一下left < n或right < n是否成立。我见过很多初学者直接在代码里写：

if arr[2 * i + 1] > arr[largest]: ...

这在2*i+1超出数组长度时直接越界，程序崩溃。正确的写法永远是先判断下标范围，再比较值。尤其注意右孩子，不是每个节点都有右孩子。

另外还要小心建堆起点的计算。在 0-based 数组里，最后一个非叶子节点是n // 2 - 1。有些资料用的是 1-based 下标描述算法，转换到 0-based 代码时需要同时调整孩子下标和父节点下标公式。如果没转对，三个下标全乱，写出来的代码会非常诡异。

6.2 递归版与迭代版 heapify 的选择

heapify用递归写起来很简洁，而且它的递归深度是二叉堆的高度 O(log n)，对于常规数据规模完全不会触发栈溢出。但在性能要求严格的时候，递归调用本身有开销。我在工程上更习惯用迭代版本：

def heapify(arr, n, i): while True: largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest == i: break arr[i], arr[largest] = arr[largest], arr[i] i = largest

这个版本把递归改成了循环，逻辑完全一致，但避免了函数调用的开销。这两种写法在思路上没有区别，只是执行方式不同。

6.3 什么时候别自己写堆排序

写代码这么多年，我的原则是：能用内置库就用内置库。Python 有heapq，Java 有PriorityQueue，C++ 有priority_queue。这些库是被大量项目验证过的，性能和边界都比自己写的更可靠。尤其是你把数据插入、弹出一堆操作混在一起的时候，手写堆容易出现各种细小的下标错误，排查起来很痛苦。

需要自己实现堆排序或者堆的场景，基本是这三种：

• 算法面试或考试，要求手写堆排序。
• 需要对底层比较逻辑做深度定制，内置堆不能满足。比如要维护一个“取最小值但带有权重等额外条件”的复杂结构。
• 平台或运行环境不允许使用标准库的某些容器。

还有一个小技巧：Python 的heapq只实现了最小堆。如果你想要最大堆，最简单的办法是把所有元素取负数放进去。这个技巧在刷题和业务代码里都特别好用。

我看过很多人写排序代码时，明明只是要从一批数据里反复取最大值，却用sort把整个数组反复排序。这本质上是对复杂度的认识不够。理解了堆排序之后，你会自然地在脑子里多装一个工具：遇到“动态极值”类问题，优先想到堆；遇到“把一个数组整理成完全有序”这种真正排序问题，再去考虑快排、归并或者内置的sort。这才是堆排序留给我们最有价值的东西。