如果你准备过算法相关的内容大概率绕不开“排序”这个专题而堆排序Heap sort又是其中比较特别的一个。它不像快排那样靠分治思想横扫千军也不像归并那样需要额外空间来换稳定它靠的是一棵完全二叉树的结构把数组在逻辑上“搭”成一个堆然后反复取堆顶完成排序。这也是堆排序最让我着迷的地方明明是在一份数组上操作代码里没有任何真实的树节点却能把大小关系维护得明明白白。这篇文章我会按照自己踩坑之后的复盘思路来写先讲清楚堆这个数据结构到底在干嘛再拆解建堆和堆化两个核心动作然后给出可以直接抄作业的代码实现最后聊一聊复杂度、稳定性以及那些我写错过的边界条件。内容对刚接触堆排序的读者会稍微友好一些但就算你已经写过几遍我也想帮你把“为什么这么写才对”这个层次补上。1. 堆排序的底层模型先忘掉排序把数组看成一颗树很多人第一次接触堆排序会很困惑数组明明是一排连续的元素怎么跟“堆”扯上关系这里的关键在于我们用下标把数组映射成了一棵完全二叉树而不是真的去构建一棵树。这种映射一旦理解透了后面的代码就是顺水推舟的事。1.1 数组与完全二叉树的映射关系对于长度为 n 的数组当我们从下标 0 开始存储元素时任意下标 i 的节点它的左孩子下标是2 * i 1右孩子下标是2 * i 2父节点下标是(i - 1) / 2。这套公式是所有堆操作的地基每次写代码前在心里过一遍而不是临时去推会省掉很多低级错误。举个例子数组[9, 5, 8, 2, 3, 7, 6]下标 0 的元素 9 是根下标 1 的 5 和下标 2 的 8 是它的左右孩子下标 3 的 2 和下标 4 的 3 是下标 1 的孩子下标 5 的 7 和下标 6 的 6 是下标 2 的孩子。你把这几个点连起来画一下会得到一棵结构很规整的树。为什么强调“完全二叉树”因为数组存储天然就是逐层从左往右填满节点这正好满足完全二叉树的定义除了最后一层每一层都是满的最后一层节点尽量靠左。把这个映射关系写成代码其实也特别简单但恰恰是这种简单中容易藏着问题。最常见的一个坑是很多人会把2 * i 1记成2 * i当数组从 0 开始时整个关系就全部错位。所以我在写堆排序前习惯先在注释里把三个公式写出来再动键盘这个小习惯让我少排查了很多恼人的逻辑问题。1.2 大顶堆和小顶堆排序方向的开关堆本身分两类大顶堆max heap满足每个节点的值都大于等于它的孩子节点堆顶就是整个数组的最大值小顶堆则相反每个节点的值小于等于孩子堆顶是最小值。堆排序默认使用大顶堆来完成升序排序这个选择乍一看可能奇怪既然要升序为什么不直接用小顶堆从头取最小值原因得从原地排序的角度想。小顶堆的堆顶确实是最小值但你把它取出来之后剩下的 n-1 个元素如果还想继续用堆排序就需要腾出额外的空间来存放取出的元素这就破坏了原地排序的诉求。反过来大顶堆的堆顶是最大值我们可以把这个最大值直接和数组末尾的元素交换相当于把最大值“推”到最终位置同时把数组的有效范围缩短一个。等到有效范围只剩一个元素时整个数组已经是升序了。这个“交换到末尾再缩小范围”的思路是堆排序的精髓也是它能做到 O(1) 额外空间的关键。如果你要的是降序结果那就反过来用小顶堆每次把最小值放到末尾。一句话记法升序用大顶堆降序用小顶堆。这个方向感一定要先立住否则看代码时会觉得逻辑怎么都是拧巴的。1.3 堆排序的适用边界它擅长什么场景堆排序的优势和软肋都非常明显这一点在实际工程里很重要。它的最坏时间复杂度是 O(n log n)这比快排在极端情况下的 O(n²) 要稳定同时它的空间复杂度是 O(1)不像归并排序需要额外开数组。如果你在写一些对稳定性要求不高、又希望在最坏情况下也能有可靠表现的排序逻辑堆排序是一个能托底的选择。但它的局限性也很刺眼。第一它不稳定相同元素的相对顺序在堆化过程中可能被打乱所以它不适合需要稳定排序的业务场景。第二它的常数因子比较大虽然复杂度量级是 O(n log n)但实际运行时间通常比快排要慢一些因为数组访问的跨度很大缓存命中率不够好看。第三它是一个“全局性”很强的排序插入新元素后需要重新维护堆结构所以它更适合动态数据的中位数、Top K 这类场景而不是单纯的通用排序。我自己的判断是堆排序最值得学的部分并不是“排序”本身而是它训练了我们用下标去模拟树结构的能力以及那种“每次只取一个最值、再修复结构”的增量式思维。这种思维优先级队列、调度系统里到处都是。2. 堆化的魔法一个函数撑起整个算法堆排序的代码看起来分两段一段是建堆一段是排序但核心其实只有一个动作堆化heapify也叫下沉sift-down。如果你能把堆化彻底写对、写透堆排序基本就拿下了大半。2.1 堆化到底在干什么把“错位”的节点一路送下去堆化处理的场景是这样的某个节点破坏了堆的性质它的值小于自己某个孩子对大顶堆来说这时候我们需要把它往下沉直到它找到了一个合适的位置。具体做法是找到当前节点和它左右孩子中最大的那个如果最大的是孩子就交换节点和孩子然后继续在这个孩子的位置上重复这个过程。用生活化的方式理解就像一队人按身高排队要求每个队长都不能比队员矮。如果某个队长站错了位置比自己的队员矮我们就让队伍里最高的队员顶上去当队长原来的队长下放到下一层。到了下一层如果他发现新的队员里还有人比自己高那就继续换直到他下面没有更高的队员了。这个过程每交换一次当前节点就往下走一层最坏情况下要走到底所以单次堆化的时间代价是 O(log n)因为树的深度就是 O(log n)。这里有一个特别关键的细节堆化只处理“从上往下的错位”它不关心当前节点上面的节点是否满足堆性质。所以你会发现如果直接对一个乱序数组从根节点开始做一次堆化整棵树并不会变成堆。真正建堆时我们必须保证所有子树先满足堆性质这引出了下一小节的自底向上策略。2.2 自底向上建堆为什么从 n/2-1 开始倒着做给定一个乱序数组怎么用有限的堆化操作让它变成大顶堆标准做法是从最后一个非叶子节点开始一直往上循环堆化。最后一个非叶子节点的下标是n/2 - 1因为最后一个节点下标是n-1它的父节点就是(n-1-1)/2 n/2-1整数除法。从它开始倒着遍历到 0逐层往上保证每个局部都满足堆性质。有人可能会问为什么不从数组末尾往前把所有节点都堆化一遍完全可以但从叶子节点开始堆化是没有意义的因为叶子节点没有孩子天然满足堆性质。我们只需要从最后一个非叶子节点往前处理就能省掉一半没有必要的调用。为什么从后往前效果是对的这背后其实是一个递归的默契。当我们处理节点 i 时因为是从后往前节点 i 的左子树和右子树已经在之前的循环里被处理过了已经满足堆性质。这时候对 i 做一次堆化即便 i 的值很小它最多下沉到叶子下沉过程中也不会破坏下面的子树结构因为被交换上去的孩子本来就是这个子树里最大的节点。这样一次堆化完成后以 i 为根的整体就变成了合法堆。一步一步往前推到根节点时整棵树就全合法了。2.3 排序阶段的循环交换两个关键位置再做一次“缩小版”堆化数组变成大顶堆之后排序阶段其实非常机械。因为大顶堆的根节点一定是整个数组的最大值我们把它和当前有效范围内的最后一个元素交换。这个元素也许是末尾原本的元素也许是从前面“沉”下来的某个小值但交换完之后最大值就被放到了最终位置也就是说它不会再参与后续操作。接下来我们只需要让新的根节点重新堆化注意堆化的范围要排除已经被“锁定”在末尾的最大元素。这个过程用一个循环表达从i n-1开始每次都把根节点和arr[i]交换然后对范围[0, i-1]内的 0 号节点做堆化然后i--。等到 i 变成 0排序就结束了因为只剩一个元素时它天然有序。注意这里的堆化范围在不断缩短我们真正比较和交换的永远是数组的“有效前缀”后半部分已经排好序的元素碰都不会碰。有一个细节值得单独拎出来说在排序阶段我们每次把堆顶换到末尾末尾那个原元素会被换到堆顶。这个元素通常比较小所以它大概率要一路下沉很多层。这就是为什么单次堆化最坏是 O(log n)整个排序阶段是 O(n log n) 的来源。而建堆阶段虽然也调用了堆化但总的代价只是 O(n)这一点我们放到章节 4 里去展开推导。3. 手写堆排序两版参考实现与避坑清单理论说得再多落到代码上才能暴露问题。这一节我会给出 C 和 Python 两个版本的实现然后逐段讲解关键步骤的必要性最后把我在实际手写过程中多次踩过的坑集中列出来。3.1 C 版本从下标公式到完整代码以下是我常用的 C 实现采用大顶堆做升序排序。#include vector #include algorithm using namespace std; // 下沉操作对以 i 为根的子树在大小限制 n 内维护大顶堆性质 void siftDown(vectorint arr, int n, int i) { while (true) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest i) { break; // 当前位置已经比两个孩子大说明无需继续下沉 } swap(arr[i], arr[largest]); i largest; // 节点换下去了下一轮继续处理它的新位置 } } void heapSort(vectorint arr) { int n (int)arr.size(); // 建堆从最后一个非叶子节点往前处理 for (int i n / 2 - 1; i 0; --i) { siftDown(arr, n, i); } // 排序把堆顶最大值放到末尾然后缩小有效范围重新堆化 for (int i n - 1; i 0; --i) { swap(arr[0], arr[i]); siftDown(arr, i, 0); } }这里没有用递归直接用while (true)循环做下沉。原因是递归在堆化时的深度可能接近log n正常情况下没问题但如果在某些嵌入式或栈受限的场景下迭代版本会更稳。更重要的是迭代版本的运行顺序更直观很多人调试递归堆化时总会有一种“它到底什么时候停”的迷惑感后面我会在问题排查里提一个实际案例。建堆循环从n / 2 - 1开始到0结束是因为这些是非叶子节点。最后一个叶子节点是n-1它的父节点是(n-1-1)/2也就是n/2-1。如果我们写for (int i n / 2; i 0; --i)其实多处理了一个没有意义的节点虽然代码不一定会错但会让初学者对“最后一棵子树从哪里开始”产生错误理解。排序循环里每次交换后调siftDown(arr, i, 0)这里的第二个参数是有效范围的长度写i而不是n是因为交换到末尾的元素已经不再参与堆调整了。3.2 Python 版本索引细节与切片陷阱Python 的代码结构类似但因为语言特性不同有几个特有的注意点。def sift_down(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 def heap_sort(arr): n len(arr) # 建堆 for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i) # 排序 for i in range(n - 1, 0, -1): arr[0], arr[i] arr[i], arr[0] sift_down(arr, i, 0)Python 中最容易犯的一个毛病是在heap_sort里使用arr[:i]之类的切片操作子数组然后对新数组做堆化结果原数组完全没被修改排序等于白做。堆排序的原地属性要求我们“模拟范围”而不是“创建范围”。所有对孩子下标的比较都要用left n和right n来判断是否越界而不是依赖 Python 的负索引否则下标会从后往前绕产生难以察觉的逻辑错误。还有一个性能上的小建议Python 的元组交换在堆化过程中很简洁但在循环内部频繁交换也有开销。如果你处理的数据规模很大可以考虑在sift_down里先记录最大的下标、一次性交换这是更贴近底层实现的做法。上面这个版本已经采用了这个风格看起来更啰嗦但实际更稳。3.3 手写时最容易写错的四个细节我复盘过自己教别人的经验也观察过一些初学者手写堆排序的常见错误集中体现在以下几个方面每一条都是针对“看起来代码没问题但结果不对”的急救排查点。下标公式混用数组从 0 开始时孩子下标是2i1和2i2而不是2i和2i1。这个错误会导致整个树的映射关系错位建堆结果必然不对。堆化范围忘记收缩建堆结束后进入排序循环每次交换堆顶和arr[i]之后再堆化时传的长度必须是i不是原来的n。否则已经放到末尾的最大值会被重新纳入比较等于白排序。建堆起始下标少减一n // 2 - 1才是最后一个非叶子节点写n // 2虽然可能也能糊弄过去但说明你还没理解父下标公式。递归堆化没有终止条件或忘了更新当前节点如果你非要用递归写法siftDown函数里递归调用后的参数必须是largest而不是i否则会陷入无限递归。这个错误在初学时特别常见我在下面一节的排查实录里会再补一个例子。我记得有一次帮某同事排查堆排序他的代码用了递归但是递归参数写成了i结果程序一直跑不出结果。单步跟踪后发现交换完之后他又对原来的节点位置做递归相当于每次换完发现这个位置还是局部最大就原地递归最终栈溢出。换成largest之后立刻正常了。这种细节不亲自踩一遍真的很难记住。4. 复杂度、稳定性与横向对比为什么它不如快排流行我们写排序算法时除了“能排出来”以外复杂度、稳定性、常数因子和缓存友好度都会影响实际选择。堆排序在这几个维度上的表现非常刻画清晰但也正因为如此它在通用排序场景里并不比快排受欢迎。理解这些表现对你判断何时改用堆排序很有帮助。4.1 建堆为什么是 O(n)排序阶段为什么是 O(n log n)先看建堆。假设堆有 h 层叶子层在第 0 层根在第 h 层。我们对倒数第二层的节点做堆化时最坏下沉一层对倒数第三层做堆化时最坏下沉两层对第 k 层的每个节点最坏下沉 h-k 层。第 k 层大约有 2^k 个节点所以建堆总操作量约等于[ \sum_{k0}^{h-1} 2^k \cdot (h-k) ]这个和式可以通过错位相减化简最终结果是 (2^{h1} - h - 2)而 h 是 O(log n)所以整体是 O(n)。关键原因在于越靠近树底部的节点数量越多但它们需要下沉的深度越浅越靠近根的节点数量少虽然下沉深度深但贡献很小。这跟“从根开始一个一个插入建堆”是 O(n log n) 有本质区别。再看排序阶段。每取一个最大值放到末尾都要对根节点重新做一次堆化根节点下沉深度最坏是当前堆的高度 O(log n)。这一步要做 n-1 次所以排序阶段一定是 O(n log n)。整个堆排序的总复杂度就由排序阶段主导平均、最好、最坏都是 O(n log n)。空间复杂度上迭代版的额外变量是常数级所以是 O(1) 的原地排序。4.2 为什么堆排序不稳定一个简单例子说明白稳定排序的要求是如果两个元素的值相等它们在排序前后的相对顺序不能变。堆排序不满足这个要求原因在于堆化过程会把元素从比较远的位置搬到比较远的位置。用一个例子来演示会更直观。数组[5a, 5b, 2]其中5a和5b是值相等的两个元素但为了区分我给他们写了编号。建堆后下标 1 的5b和下标 2 的2比较最大值还是下标 1下标 0 的5a和下标 1 的5b比较因为arr[1] arr[0]不成立所以不需要交换。这样看上去好像没有打乱顺序。但如果是[2, 5a, 5b, 1]呢建堆过程中可能先把5a换到某个位置又把5b换过去两个相同元素的相对位置就不一定保得住了。这也是我在实际业务中很少用堆排序做需要稳定输出的原因。如果业务上要求相同 key 的元素保持原始顺序那要么用归并排序要么给每个元素加一个序号作为次关键字人为制造可比较的顺序。4.3 快排、归并、堆排怎么选一张表看清边界很多情况下我们其实不需要“最优排序”只需要“够用且适合当前场景”。这里我给一个横向对比表方便你在写代码时快速决策。维度堆排序快速排序归并排序平均时间复杂度O(n log n)O(n log n)O(n log n)最坏时间复杂度O(n log n)O(n²)O(n log n)空间复杂度O(1)O(log n) 栈空间O(n)稳定性不稳定不稳定稳定缓存友好度较差较好一般主要适用场景需要最坏保证且省内存Top K优先级调度通用排序首选需要稳定的通用排序从表里能看出堆排序最大的“卖点”是最坏情况下也有 O(n log n) 的时间且空间复杂度是 O(1)。所以它在嵌入式环境、以及对“最坏响应时间”有要求的系统里确实有不可替代的位置。而在通用库函数里比如常见的排序库大多采用快排或者快排与插入排序的混合策略因为平均性能更好、缓存更友好。归并排序则因为稳定被用于对象排序的场景。我还想单独提一个点那就是堆排序的“增量”特性。虽然堆排序本身不是稳定的但它天然支持优先队列操作以 O(log n) 的代价插入元素、取最值。所以在大数据处理中我们更多是使用堆的变体——比如小顶堆维护 Top K而不是用完整的堆排序流程一遍又一遍排序。这种“部分排序”的思路其实比完整排序更贴近真实需求。5. 常见问题与排查技巧实录写算法时最痛苦的不是不懂原理而是明明觉得代码没问题结果却不对。堆排序因为涉及下标、范围、递归/迭代多个变量的联合作用出错的概率并不低。下面这些是我和找我请教的人经常遇到的问题我把它们整理成一份速查式排查清单。5.1 建堆结束后数组还不是大顶堆怎么查如果你在建堆循环之后打印数组发现某个父节点还是小于孩子那大概率是建堆的起始位置或循环方向出了问题。请确认你的循环是for (int i n/2-1; i 0; --i)这样的倒序而不是for (int i 0; i n/2-1; i)的正序。这里为什么不能正序因为正序遍历时前面的子树还没建好你处理一个节点 i 时它的孩子子树不一定满足堆性质那么下沉时即使某个孩子是子树里的“局部最大”这个局部的下部分依然是乱序的处理上去就没有意义。倒序遍历保证每一个 i 处理时它的左右子树已经是合法的堆了这时候下沉一次就能保证以 i 为根的整个子树全合法。另外边界判断也要仔细。比如下标为n-1的叶子节点它的父节点下标是(n-2)/2。对于 n 是奇数时n/2-1和(n-2)/2是同一个数对于 n 是偶数时末尾是一个左孩子父节点也是n/2-1。所以统一从n/2-1开始是最安全的不容易写错。5.2 排序结果顺序不对八成是范围控制的问题排序阶段最典型的症状是数组前半部分排好了后半部分也基本有序但中间某处突然出现一个特别小或者特别大的值。我排查过不少这样的案例根因都是堆化范围没有正确缩小。在交换堆顶和arr[i]之后堆化函数需要传i而不是n这一点前面提过但这里还是想再强调一次因为它的后果有迷惑性如果你传了n已经排到末尾的大元素会被重新放回堆中下次很可能又被交换出来导致排序结果一波三折。更隐蔽的一个问题是排序阶段开始时数组确实是个合法的堆但交换根和末尾后新的根节点往往很小。这时候如果堆化函数写错没有比较两个孩子而是只比较了左孩子那么右孩子可能比新根大但没被处理导致堆性质在某一层失效排序结果就局部错乱。因此我建议写堆化时先比较左孩子更新 largest再比较右孩子更新 largest两次比较缺一不可。5.3 递归堆化导致栈溢出或死循环递归写法最容易出两个问题一是递归终止条件写错二是在交换之后递归参数传错。前者会导致无限递归直接栈溢出后者会让程序在某个节点原地转圈、看似卡死实际也是无限递归。一个非常隐蔽的终止条件问题是有些人会在函数开头写if (i n) return;但又忘了在两个孩子都超出范围时也要退出。更稳妥的写法其实是先找出 largest如果 largest 等于 i就立即结束递归因为这时候节点和两个孩子的关系已经满足要求不需要进一步下沉。如果 largest 不等于 i交换后递归调用siftDown(arr, n, largest)这里必须传 largest不能传 i。这个细节我在前面提到过一遍但因为它太容易踩到我宁可再重复一次提醒你。如果你不想和递归纠缠直接用第一节里的迭代版本可以完全避免这类问题。迭代版本天然通过break退出循环没有递归深度的问题也不会出现“递归调用参数写错”的隐患。我在自己编写的工具代码里默认都使用迭代版。5.4 堆化操作在优先队列和 Top K 问题中的变体用法堆排序真正的用武之地往往不在“完整排序”本身而在优先队列和部分排序。最典型的就是 Top K 问题从海量数据里找出最大的 K 个元素。做法是维护一个大小为 K 的小顶堆堆顶是当前入选的 K 个元素中最小的那个。新元素进来时如果它比堆顶大就把堆顶替换掉然后对新根做一次下沉。遍历完全部数据后堆里的 K 个元素就是最终答案。这个场景如果用堆排序完整版来处理会非常浪费因为完整排序是 O(n log n)而 Top K 用小顶堆只需 O(n log K)。当 K 远小于 n 时效率差异非常明显。这也是堆结构在工程里更常见的形态——优先队列。从这个角度看理解堆排序的价值其实是理解“维护一个局部有序的结构按需取最值”的思维而不是单纯地背代码。我再补充一个使用变体时的注意点小顶堆的堆化函数和大顶堆的方向相反比较时是找左右孩子中更小的那个。如果你直接复制大顶堆代码然后改符号容易漏掉初始化的位置务必把 largest 改成 smallest 并且在两个比较分支里都用小于号否则结果会错得非常离谱。5.5 排序前先复制一份原数据调试阶段的低成本防坑最后一条经验跟代码正确性无关但跟调试效率密切相关。堆排序是原地排序你一旦执行原数组就被打乱了。如果你在调试过程中想对比“排序前的数据”和“排序后的数据”发现原数据已经不存在了就得重新生成一份。这不是堆排序独有的问题但堆排序的调试过程经常需要反复观察“建堆前”和“建堆后”的差别丢失原始数据会特别耽误时间。我一般的做法是在写实验代码或白板题时先auto backup arr;复制一份然后放心大胆地原地操作。等确认逻辑没问题再删掉备份。这个小习惯不花多少时间却能在你一头雾水的时候让你快速回退到之前的现场而不是靠记忆里那个乱七八糟的数组去猜。6. 最后再分享一点实战体会如果问我堆排序在整个算法体系里最值得记住的教训是什么我会说是“用数组模拟树”的思维转换。它让我不再把数据结构看成一堆死板的节点而是看成一堆下标关系的组合。堆排序的每一行代码本质上都是在维护一棵看不见的树。这种抽象能力比单纯记住某个排序流程更有价值。从我个人的实测经验来看堆排序的代码量不大但手写一遍、调试一遍、再根据自己的习惯改写成迭代版这个过程走完你对递归、下标、边界条件的掌控会上一个台阶。我通常建议别人先照着代码敲一遍然后关掉编辑器从空文件重新写直到能一次写对。这个“盲写”练习虽然有点枯燥但能暴露出大量你以为自己懂了、其实没懂的地方。如果你之后还要接触更高阶的内容比如优先队列、图的最短路算法、调度器设计你会发现堆排序里的堆化思想无处不在。希望这篇内容能帮你把最底层的那块砖夯实后面盖楼的时候会更踏实。