堆排序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]来走一遍完整建堆。数组长度 n8最后一个非叶子节点下标是 8 // 2 - 1 3对应的值是 1。从下标 3 开始往前调整i3值 1左右孩子是下标 7 的值 4。孩子 4 大于 1交换得到[7, 3, 8, 4, 5, 2, 6, 1]。此时下标 7 是叶子下沉结束。i2值 8左右孩子是下标 5 的值 2 和下标 6 的值 6。8 最大不动。i1值 3左右孩子是下标 3 的值 4 和下标 4 的值 5。5 最大交换得到[7, 5, 8, 4, 3, 2, 6, 1]。继续看下标 4值 3已是叶子结束。i0值 7左右孩子是下标 1 的值 5 和下标 2 的值 8。8 最大交换得到[8, 5, 7, 4, 3, 2, 6, 1]。再看下标 2值 7左右孩子下标 5 的值 2 和下标 6 的值 67 还是最大结束。建堆结果是大顶堆[8, 5, 7, 4, 3, 2, 6, 1]。你可以验证每个父节点都大于等于子节点8 大于 5 和 75 大于 4 和 37 大于 2 和 64 大于 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 2i1、parent i//2而实际编程语言基本都是 0-based关系变成 left 2i1、right 2i2、parent (i-1)//2。这个转换是新手第一个翻车点。看教程时觉得懂了一写代码发现数组越界或者建堆时从 n//2 而不是 n//2 - 1 开始结果根节点没被调整。我建议你选定一套下标体系后就死记一套公式不要混着用。写代码时给自己一个固定模板0-based、left 2i1、right 2i2、建堆起点 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 排查速查表我自己在实际调试堆排序时踩过的坑整理成表格遇到问题可以对着自查。问题现象可能原因排查与解法数组越界异常下沉时未检查 left/right 是否小于 n在访问 a[left] 和 a[right] 前一定加边界判断排序结果不完整最大值没到末尾排序阶段下沉时使用了原始数组长度下沉函数必须接收有效边界 end而不是永远传 n排序结果部分有序根附近混乱建堆起点写成了 n//2 而不是 n//2 - 1最后一个非叶子节点是 n//2 - 1根节点也要参与调整程序死循环下沉循环缺少退出条件当 largest 等于当前 i 时立即 break元素被重复交换结果不稳定建堆或排序阶段比较条件用了大于等于想维护稳定性要额外处理堆排序不改比较条件仍会乱序大数组递归版本报栈溢出下沉写成了递归改成 while 循环迭代实现5. 从单机到工程堆排序的边界与变体5.1 不同语言的实现要点如果你用 Cstd::make_heap、std::pop_heap、std::sort_heap其实已经把堆排序封装好了但面试手写时通常要求自己实现。C 里要特别注意迭代器边界类型上多用vectorint作为入参避免值传递的额外拷贝。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。把有效长度作为显式参数传入能避免一类非常隐蔽的边界错误。最后建议你对比着看堆排序和快速排序的代码感受两者的权衡。快排的平均性能更好但不稳定排序且最坏退化堆排序性能稳定但常数大。把这种工程设计层面的权衡说清楚比单纯讲清楚一个算法更能体现一个开发者的功力。这也是为什么堆排序作为“十大经典”里的常客值得你花一个下午彻底吃透。 
长河君 · 2026/10/17 12:11:02 · 阅读 1.2k 堆排序实战详解：从完全二叉树构建最大堆到原地排序的算法原理与面试要点
堆排序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]来走一遍完整建堆。数组长度 n8最后一个非叶子节点下标是 8 // 2 - 1 3对应的值是 1。从下标 3 开始往前调整i3值 1左右孩子是下标 7 的值 4。孩子 4 大于 1交换得到[7, 3, 8, 4, 5, 2, 6, 1]。此时下标 7 是叶子下沉结束。i2值 8左右孩子是下标 5 的值 2 和下标 6 的值 6。8 最大不动。i1值 3左右孩子是下标 3 的值 4 和下标 4 的值 5。5 最大交换得到[7, 5, 8, 4, 3, 2, 6, 1]。继续看下标 4值 3已是叶子结束。i0值 7左右孩子是下标 1 的值 5 和下标 2 的值 8。8 最大交换得到[8, 5, 7, 4, 3, 2, 6, 1]。再看下标 2值 7左右孩子下标 5 的值 2 和下标 6 的值 67 还是最大结束。建堆结果是大顶堆[8, 5, 7, 4, 3, 2, 6, 1]。你可以验证每个父节点都大于等于子节点8 大于 5 和 75 大于 4 和 37 大于 2 和 64 大于 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 2i1、parent i//2而实际编程语言基本都是 0-based关系变成 left 2i1、right 2i2、parent (i-1)//2。这个转换是新手第一个翻车点。看教程时觉得懂了一写代码发现数组越界或者建堆时从 n//2 而不是 n//2 - 1 开始结果根节点没被调整。我建议你选定一套下标体系后就死记一套公式不要混着用。写代码时给自己一个固定模板0-based、left 2i1、right 2i2、建堆起点 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 排查速查表我自己在实际调试堆排序时踩过的坑整理成表格遇到问题可以对着自查。问题现象可能原因排查与解法数组越界异常下沉时未检查 left/right 是否小于 n在访问 a[left] 和 a[right] 前一定加边界判断排序结果不完整最大值没到末尾排序阶段下沉时使用了原始数组长度下沉函数必须接收有效边界 end而不是永远传 n排序结果部分有序根附近混乱建堆起点写成了 n//2 而不是 n//2 - 1最后一个非叶子节点是 n//2 - 1根节点也要参与调整程序死循环下沉循环缺少退出条件当 largest 等于当前 i 时立即 break元素被重复交换结果不稳定建堆或排序阶段比较条件用了大于等于想维护稳定性要额外处理堆排序不改比较条件仍会乱序大数组递归版本报栈溢出下沉写成了递归改成 while 循环迭代实现5. 从单机到工程堆排序的边界与变体5.1 不同语言的实现要点如果你用 Cstd::make_heap、std::pop_heap、std::sort_heap其实已经把堆排序封装好了但面试手写时通常要求自己实现。C 里要特别注意迭代器边界类型上多用vectorint作为入参避免值传递的额外拷贝。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。把有效长度作为显式参数传入能避免一类非常隐蔽的边界错误。最后建议你对比着看堆排序和快速排序的代码感受两者的权衡。快排的平均性能更好但不稳定排序且最坏退化堆排序性能稳定但常数大。把这种工程设计层面的权衡说清楚比单纯讲清楚一个算法更能体现一个开发者的功力。这也是为什么堆排序作为“十大经典”里的常客值得你花一个下午彻底吃透。