企业官网建设流程全解析

堆排序（Heap Sort）这个名字，听起来像是堆结构的一种附属操作，其实它是一整套基于完全二叉树构建最大堆、然后反复取堆顶完成排序的算法。作为十大经典排序算法里唯一一个能在最坏情况下保持 O(n log n) 时间复杂度、同时又做到 O(1) 额外空间的原地震荡排序，它常被面试官拿来考察候选人到底有没有真正理解堆结构，而不只是背代码。

如果你正准备算法面试、复习数据结构，或者工作中需要处理大量内存受限的排序任务，这篇文章就是冲着“一次讲透”来的。我会先拆思路，再讲两个核心操作，然后展示完整代码和手工推演，最后把容易踩的坑和排查技巧一条条列出来。老实说，堆排序入门时有几个坎儿非常隐蔽，当初我自己也绕了很久，这些我都会在下面写清楚。

1. 设计思路拆解：为什么堆排序能排在“十大经典”里

1.1 从“选择排序的聪明改进”说起

先回到最朴素的选择排序：每次从头到尾扫一遍，找到最小值放到前面，重复 n 次，时间复杂度是 O(n²)。浪费在哪里？每一次“找最小值”都要把整个数组再扫一遍，而前面扫描得到的比较结果完全没有被记下来。

堆排序的思路就是从这里升级的：它用一个“堆”把比较结果持久化地保存下来。堆不是一段额外的大空间，而是把数组本身当成一棵完全二叉树来组织。这样一来，找到最大值只需要看一眼根节点，得到最大值之后，也只需要做一次 O(log n) 的下沉调整，就能维持新的堆结构。相当于把每轮查找最大值从 O(n) 降到了 O(log n)，整体就是 O(n log n)。

关键点在于：堆排序没有借助额外的数组，所有操作都在原数组上完成，这是它区别于归并排序的最重要特征。归并排序虽然也是 O(n log n)，但它需要 O(n) 的辅助空间，在某些内存受限的嵌入式场景里是硬伤。堆排序的 O(1) 额外空间，让它在资源受限环境里一直有存在感。

1.2 数组如何变成“堆”：完全二叉树与下标关系

堆排序依赖的“完全二叉树”，并不是真实建树，而是通过数组下标映射出来的逻辑结构。假设数组长度为 n，下标从 0 开始，那么对任意下标 i：

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

这个映射关系是整个堆排序的地基。你可能觉得它很简单，但真正写代码时，一半以上的 bug 都出在这个公式的边界上。比如 i 已经是叶子节点时，2 * i + 1 可能大于 n，访问就会越界，所以调整的循环条件里必须先判断 child < n。

大顶堆的定义也很直白：对任意父节点 i，它的值必须大于等于左右子节点。一旦违反这个规则，就需要“下沉”调整。整个过程可以理解为在数组上不断维护这个规则，让最大值最终浮到根节点。

1.3 升序用大顶堆，降序用小顶堆

堆排序里最容易懵的一个方向问题：要排升序，为什么用的是大顶堆？

因为堆排序的思路是“每次取最大值放到末尾”。先构建一个大顶堆，此时堆顶是全局最大值，把它和数组最后一个元素交换，最大值就住进了它最终的位置。然后数组的有效长度减一，对新的堆顶再做下沉调整，重新得到大顶堆，再交换……循环 n-1 次，数组就是升序了。

反过来，如果要降序排列，就构建小顶堆，每次把最小值放到末尾。你只需要把堆调整时的大小比较方向反过来即可。记住这个结论可以少走弯路，代码层面改差异很小，但方向错了，排序结果会完全反掉。

2. 核心细节解析与实操要点

2.1 两个核心操作：上浮与下沉

堆结构有两个基本调整操作：上浮（swim）和下沉（sink）。上浮用于插入新元素时，把新元素一路和父节点比较，不满足堆序就和父节点交换，直到稳定为止。下沉用于删除堆顶或调整某个节点时，把该节点一路和较大的子节点比较，然后交换到合适位置。

这里必须强调：堆排序的主体只用下沉，不用上浮。原因很直接——堆排序是从一个无序数组“原地建堆”，建堆过程是自底向上对每个非叶子节点做下沉，而不是一个一个插入。这一点是很多人的认知误区。面试时如果你回答说堆排序用到了插入和上浮，对面基本就判断你只是背了代码。

下沉的写法里有个细节值得展开：到底该先比左孩子还是右孩子？最稳的写法是左右孩子都看一遍，先假设当前节点是最大，用两个 if 分别比较左右孩子，最后把 largest 更新成实际最大的下标。不要想当然“先左后右”就固定交换左孩子，因为右孩子可能更大，顺序错了堆序就坏了。

2.2 建堆为什么从 n/2 - 1 开始

这是堆排序里被问得最多的问题。数组长度为 n，最后一个非叶子节点的下标是多少？答案是 n // 2 - 1（对应索引从 0 开始的情况）。原因是最后一个元素的下标是 n-1，它的父节点是 ((n-1) - 1) // 2，也就是 (n-2)//2，计算结果就是 n//2 - 1。

逻辑上，叶子节点没有子节点，下沉操作对它没有意义，所以建堆只需要从最后一个非叶子节点开始，往前遍历到根节点。这也是建堆复杂度能做到 O(n) 而不是 O(n log n) 的原因之一。很多人以为“建堆也要 O(n log n)”，其实不然，我在后面复杂度一节会详细算给你看。

代码上对应这段：

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

第一次接触的人很容易写错 range 的结束位置。注意range(a, -1, -1)会包含 0，这是一个左闭右开结构的反向遍历，结束值 -1 不取，但 0 会取到，所以根节点也会被调整。

2.3 排序阶段：交换、缩界、再下沉

建堆完成后，堆顶已经是最大值了。此时把堆顶和数组末尾交换，最大值就到了最终位置。然后数组的“有效堆长度”从 n 变成 n-1，对新的堆顶再做下沉，恢复大顶堆。再次交换、再次下沉，循环往复。

这里有个关键词叫“有效长度”。交换之后，末尾元素其实还在数组里，只是我们不希望它再次参与堆调整，所以要通过一个变量end或n来控制调整范围。如果我每次都用原始数组长度做调整，刚放好的最大值又会被调回堆顶，排序就乱套了。

下沉函数必须接收一个“当前堆的有效边界”参数，而不是每次都直接用数组长度。这个边界参数的传递，是堆排序代码最容易写错的地方，后面排查清单里我会再拎出来说。

2.4 完整的 Python 实现与逐行讲解

直接上一版可以跑通的迭代版代码，我建议不要用递归写下沉。原因是 Python 的递归深度限制在 1000 左右，数据量大一点，递归版直接抛异常，工程上非常不实用。迭代版虽然看着啰嗦，但健壮得多。

def heap_sort(arr): def sift_down(a, i, n): while True: largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and a[left] > a[largest]: largest = left if right < n and a[right] > a[largest]: largest = right if largest == i: break a[i], a[largest] = a[largest], a[i] i = largest n = len(arr) # 建堆：从最后一个非叶子节点开始，逐个下沉 for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n) # 排序：反复将堆顶交换到末尾，再调整剩余部分 for end in range(n - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] sift_down(arr, 0, end) return arr

逐行看三个地方：

left < n和right < n的检查绝对不能省。当某个节点只有左孩子没有右孩子时，right 下标会越界，不检查就访问数组会直接报错。尤其是排序阶段，有效堆长度一直在缩短，边界比建堆阶段更敏感。

largest == i是退出条件。它表示当前节点比左右孩子都大，已经符合大顶堆原则，不需要继续调整。如果不写这个退出条件，就会陷入死循环。

i = largest是迭代下沉的关键。交换之后，当前节点变成了 largest 位置，它可能还需要继续往下沉，所以循环要把 i 更新为 largest，不要写 return。很多新手在交换后直接 break，结果调整一半就停了。

3. 实操过程与核心环节实现

3.1 手工推演建堆全过程

纸上谈兵不如真正推演一遍。我拿一组数据[7, 3, 8, 1, 5, 2, 6, 4]来走一遍完整建堆。

数组长度 n=8，最后一个非叶子节点下标是 8 // 2 - 1 = 3，对应的值是 1。从下标 3 开始往前调整：

• i=3，值 1，左右孩子是下标 7 的值 4。孩子 4 大于 1，交换，得到[7, 3, 8, 4, 5, 2, 6, 1]。此时下标 7 是叶子，下沉结束。
• i=2，值 8，左右孩子是下标 5 的值 2 和下标 6 的值 6。8 最大，不动。
• i=1，值 3，左右孩子是下标 3 的值 4 和下标 4 的值 5。5 最大，交换，得到[7, 5, 8, 4, 3, 2, 6, 1]。继续看下标 4，值 3，已是叶子，结束。
• i=0，值 7，左右孩子是下标 1 的值 5 和下标 2 的值 8。8 最大，交换，得到[8, 5, 7, 4, 3, 2, 6, 1]。再看下标 2，值 7，左右孩子下标 5 的值 2 和下标 6 的值 6，7 还是最大，结束。

建堆结果是大顶堆[8, 5, 7, 4, 3, 2, 6, 1]。你可以验证每个父节点都大于等于子节点：8 大于 5 和 7，5 大于 4 和 3，7 大于 2 和 6，4 大于 1。到这里，堆顶的 8 就是全数组最大值。

3.2 排序阶段的逐步演示

建堆完成后进入排序阶段。我继续用上面的堆，手动走两步你就明白整体逻辑了。

第一步，交换堆顶 8 和数组末尾 1，得到[1, 5, 7, 4, 3, 2, 6, 8]，然后对前 7 个元素做下沉：1 与 5、7 比较，7 最大，交换，得到[7, 5, 1, 4, 3, 2, 6, 8]；1 继续下沉到下标 2，和 2、6 比较，6 更大，交换，得到[7, 5, 6, 4, 3, 2, 1, 8]。此时前 7 个元素又恢复为大顶堆，且堆顶是 7。

第二步，交换堆顶 7 和当前有效末尾元素 1，得到[1, 5, 6, 4, 3, 2, 7, 8]，再对前 6 个元素下沉：1 与 5、6 比较，6 最大，交换，得到[6, 5, 1, 4, 3, 2, 7, 8]；1 到下标 2 后和 4、3 比较，4 更大，交换，得到[6, 5, 4, 1, 3, 2, 7, 8]。

看到规律没有？每一轮过后，最大值就像气泡一样从堆顶被“抽”到数组末尾，同时堆的有效长度减一。整个过程不需要额外数组，原地完成，这就是堆排序最优雅的地方。

3.3 边界用例与测试方式

写完算法，验证不能只测正常数据。我的习惯是至少跑四类用例：空数组、单元素数组、含重复值的数组、已经有序的数组。

assert heap_sort([]) == [] assert heap_sort([1]) == [1] assert heap_sort([5, 3, 3, 1, 2]) == [1, 2, 3, 3, 5] assert heap_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5] assert heap_sort([9, 8, 7, 6, 5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5, 6, 7, 8, 9]

边界用例尤其能暴露出 index 的坑。空数组和单元素数组主要检查n // 2 - 1是否为负数，以及循环是否被正确跳过。事实上 Python 中for i in range(-1, -1, -1)不会执行，所以空数组和单元素数组能安全返回，这一点需要注意写其他语言时要提前 return，避免出现未定义行为。

含重复值的数组用来验证算法是否会在比较时出现死循环。如果下沉代码没有largest == i的退出条件，重复值可能导致无意义的交换，虽然不一定报错，但性能会退化，而且当你把实现改成对象数组时，可能会引发更隐蔽的问题。

4. 常见问题与排查技巧实录

4.1 索引边界问题：1-based 与 0-based 的转换

堆排序代码在不同语言里风格差异很大，根源在于数组索引从 0 开始还是从 1 开始。很多教材使用 1-based 的伪代码，父子关系是 left = 2i、right = 2i+1、parent = i//2；而实际编程语言基本都是 0-based，关系变成 left = 2i+1、right = 2i+2、parent = (i-1)//2。

这个转换是新手第一个翻车点。看教程时觉得懂了，一写代码发现数组越界，或者建堆时从 n//2 而不是 n//2 - 1 开始，结果根节点没被调整。

我建议你选定一套下标体系后就死记一套公式，不要混着用。写代码时给自己一个固定模板：0-based、left = 2i+1、right = 2i+2、建堆起点 n//2 - 1。所有语言都按这个模板翻译，不容易乱。

4.2 堆排序为什么不稳定

稳定性是排序算法的重要属性，指的是如果两个相等的元素在排序前的相对顺序保持到排序后，算法就是稳定的。堆排序是不稳定的，而且不需要构造太复杂的反例就能说明。

比如数组[5, 5a, 3]（用 5a 表示第二个 5，便于区分）。建堆时下标 1 的 5a 和下标 2 的 3 比较，5a 更大，不动；下标 0 的 5 和两个孩子比较，两个都是 5，如果你用“大于等于”作为交换条件，5 可能和 5a 交换，顺序变了。即使这里不交换，排序阶段堆顶和末尾的交换也可能让相等元素的先后关系被打乱。

所以，当你的业务排序要求保持相等元素的原始顺序时，堆排序直接排除。这也是为什么工程上的稳定排序往往会选归并排序或 Timsort，而不是堆排序。

4.3 复杂度计算正误辨析

网上对堆排序的复杂度有不少错误说法，最典型的是“建堆也要 O(n log n)”。实际上，建堆的总时间复杂度是 O(n)。原因不复杂：假设堆高为 h，第 k 层的节点数量是 2^k，每个节点下沉时最多比较 (h-k) 次。总比较次数是一个等差等比数列求和，结果收敛于 O(n)。

排序阶段才是真正的 O(n log n)：每次从堆顶抽取最大值需要 O(log n) 的下沉，共执行 n-1 次，所以总复杂度 O(n log n)。额外空间 O(1)，因为所有交换都在原数组完成。最好情况、最坏情况、平均情况都是 O(n log n)，这是堆排序区别于快速排序的重要特点——快排最坏情况会退化到 O(n²)，堆排序不会。

但代价是：堆排序的常数因子比较大，实际运行速度通常慢于快速排序。这点面试时值得主动提，能体现你真的理解理论复杂度和实际性能不是一回事。

4.4 排查速查表

我自己在实际调试堆排序时踩过的坑，整理成表格，遇到问题可以对着自查。

5. 从单机到工程：堆排序的边界与变体

5.1 不同语言的实现要点

如果你用 C++，std::make_heap、std::pop_heap、std::sort_heap其实已经把堆排序封装好了，但面试手写时通常要求自己实现。C++ 里要特别注意迭代器边界，类型上多用vector<int>&作为入参，避免值传递的额外拷贝。

Java 里没有直接暴露堆排序的内置方法，PriorityQueue虽然也是堆，但它用于动态插入场景，不能直接原地排序。自己实现时可以用递归下沉，因为 Java 没有 Python 那样的递归深度限制，但工程风格仍然建议迭代。JavaScript 则要小心比较函数的方向，如果你用(a, b) => a - b做升序，堆内比较也要保持一致，否则排序结果和预期完全相反。

核心思想在任何语言里都一样：建堆一次、交换 n-1 次、每次下沉 log n 层。语言差异只体现在语法细节和边界处理上。

5.2 工程中什么时候该用堆排序

堆排序不会像快速排序那样被用作通用排序的默认实现，但它有两个不可替代的场景。

其一是内存受限的嵌入式环境。O(1) 额外空间意味着不管数组多大，都不需要担心辅助内存溢出。其二是“只关心最大/最小几个值”的场景，也就是 TopK 问题。这时候把数据整体排序其实很浪费，用大小为 k 的小顶堆扫描一遍数组，就能拿到最大的 k 个值，时间复杂度 O(n log k)，数据量再大也能扛。

拿我从实践中得到的体会来说，很多刚学算法的人喜欢把堆排序和优先队列混为一谈。堆排序是排序算法，优先队列是数据结构，但两者共享核心的下沉和上浮逻辑。你如果能把堆排序的代码默写出来，那么优先队列的实现也等于会了一半，这个内在联系比单纯背排序代码更有价值。

5.3 我的几点实际操作经验

如果你是为了准备面试去攻克堆排序，我建议按下面的路径来练习，而不是直接背完整代码。先写十年经验的“老油条”版本也没关系，关键是你要能从零推演每一步操作。

第一步，脱离代码，在纸上画一棵完全二叉树，手动模拟下沉过程。第二步，背住 0-based 的下标公式，用一组 5~10 个数的数组至少完整推演两遍。第三步，再打开编辑器写代码，注意把sift_down的参数设计成(数组, 当前下标, 有效长度)。

这一步值得强调：参数命名和职责划分决定了你调试时的体验。如果sift_down内部用全局变量len(arr)，排序阶段必然出 bug。把有效长度作为显式参数传入，能避免一类非常隐蔽的边界错误。

最后建议你对比着看堆排序和快速排序的代码，感受两者的权衡。快排的平均性能更好，但不稳定排序且最坏退化；堆排序性能稳定但常数大。把这种工程设计层面的权衡说清楚，比单纯讲清楚一个算法更能体现一个开发者的功力。这也是为什么堆排序作为“十大经典”里的常客，值得你花一个下午彻底吃透。