★ FEATURED ARTICLE 1. 堆结构到底在解决什么问题很多人第一次接触堆是在优先队列这一章。教材上画一棵完全二叉树标上大顶堆或小顶堆的性质然后给两个函数向上调整和向下调整。考试能过代码能写但一旦让自己从零手撸一个能扛住边界情况的堆问题就全冒出来了——删除堆顶之后最后一个元素该放哪、向下调整的终止条件到底怎么写才不会越界、建堆为什么从最后一个非叶子节点倒着来而不是从根开始、堆排序里那个交换堆顶与末尾的循环边界为什么是大于零而不是大于等于零。这些细节教材往往一笔带过但它们恰恰是堆这个结构最容易翻车的地方。这篇内容就是围绕堆的维护细节展开的。核心关键词是堆、向上调整、向下调整、建堆、堆排序、优先队列。我会把堆当成一个需要长期维护的数据结构来看而不是一个考试题型。适合两类人看一类是刚学完堆的基本概念、想把它写扎实的初学者另一类是工作里要用优先队列、但一直靠标准库、想搞清楚底层到底在干什么的开发者。读完之后你应该能做到不看任何参考手写出一份边界正确的堆实现并且能解释清楚每一个循环条件为什么这么写。堆的本质是一个用数组存储的完全二叉树它只维护一个偏序关系父节点不小于或不大于子节点。注意是偏序不是全序——堆不保证左右孩子之间谁大谁小也不保证整个数组有序。这个只维护部分有序的取舍正是堆能在 O(log n) 时间内完成插入和删除堆顶、同时保持 O(1) 取极值的原因。理解这一点后面所有的维护操作就都有了统一的解释框架每一次调整都是在局部修复被破坏的偏序关系而不是在排序。我在实际带人的过程中发现堆的坑几乎全部集中在下标计算和循环边界这两件事上。所以下面的内容会反复回到这两个点上把每个操作的每一步都摊开讲。2. 存储布局与下标关系一切维护的地基2.1 为什么用数组而不是链式结构完全二叉树有一个非常好的性质除了最后一层每一层都是满的最后一层的节点全部靠左排列。这个性质意味着节点的位置是紧凑的可以用连续下标一一映射不需要存左右指针。用数组存堆省掉了指针的空间开销更重要的是获得了缓存友好性——连续内存访问在现代 CPU 上的效率远高于指针跳转。这也是为什么几乎所有标准库的优先队列底层都是数组实现的堆而不是链式的平衡树。映射规则很固定根节点放在下标 0或 1两种约定都行但混用必出事对下标为 i 的节点父节点是 (i-1)/2整数除法左孩子是 2i1右孩子是 2i2。如果根从 1 开始则父节点是 i/2左孩子 2i右孩子 2i1。注意根从 0 还是从 1 开始必须在整个项目里统一。我见过太多 bug 是因为建堆用 0 基、调整函数用 1 基结果数组访问错位小数据测试看不出来数据量一大就崩。我个人强烈建议统一用0 基。原因有两个一是绝大多数编程语言的数组天然从 0 开始用 0 基不需要在业务数据和堆内部之间做下标转换二是标准库的容器迭代器也是 0 基语义混用 1 基会在封装时引入额外的偏移计算容易出错。1 基的唯一好处是父节点计算 i/2 更简洁但这个优势在 0 基下用 (i-1)1 同样能拿到而且位运算比除法快。2.2 下标计算的几个易错点第一个易错点是整数除法的方向。0 基下父节点是 (i-1)/2当 i1 或 i2 时(i-1)/2 分别是 0 和 0正确。但如果有人写成 i/2i1 时得到 0碰巧对i2 时得到 1错2 的父节点应该是 0。这种部分正确的 bug 最阴险因为小规模测试可能刚好绕过去。第二个易错点是孩子下标的溢出。在向下调整时我们通常先算左孩子 left 2i1然后判断右孩子是否存在。如果 i 很大2i1 可能超出数组长度此时必须先判断 left n 再访问不能先访问再判断。更隐蔽的是如果 i 接近整型上限2*i 本身就会溢出成负数虽然实际堆大小很难到这个量级但在做通用库时值得用 size_t 或先做边界检查。第三个易错点是最后一个非叶子节点的下标。建堆时从它开始倒着向下调整。0 基下最后一个节点下标是 n-1它的父节点是 (n-1-1)/2 (n-2)/2也就是 n/2 - 1整数除法。很多人记成 n/2结果多调整了一个叶子节点——叶子没有孩子向下调整会直接返回虽然不出错但白跑一趟更糟的是如果写成 (n-1)/2当 n 为偶数时会漏掉一个真正需要调整的节点建堆结果就是错的。场景0 基正确写法常见错误写法后果父节点(i-1)1i1i 为偶数时父节点错位左孩子2*i12*i整体偏移一位右孩子2*i22*i1与左孩子混淆最后非叶子n/2-1(n-1)/2 或 n/2漏调或白调这张表建议直接贴在显示器边上手写堆的时候对着核一遍能省掉大量调试时间。3. 向上调整插入操作的全部秘密3.1 插入的完整流程与调整逻辑往堆里插入一个元素标准做法是把它放到数组末尾也就是完全二叉树的最后一个位置这样仍然满足完全二叉树的结构性质但可能破坏堆的偏序性质——新元素可能比它的父节点更优先。修复的办法就是向上调整不断比较当前节点和父节点如果违反堆性质就交换直到满足或者到达根。以大顶堆为例插入值 val 后从末尾下标 i 开始当 i 0 且 arr[i] arr[parent(i)] 时交换 arr[i] 和 arr[parent(i)]然后 i parent(i)继续。循环结束的条件有两个缺一不可i 到达 0没有父节点了或者当前节点已经不大于父节点偏序恢复。这里有个细节值得说清楚为什么用交换而不是上浮赋值。交换写法直观每次交换三个赋值操作另一种写法是把新元素暂存然后一路把父节点往下挪最后把新元素放到空出来的位置这样每次上移只需要一次赋值。后者在元素较大比如结构体时更高效因为减少了拷贝次数。两种写法结果完全一样选哪个看场景。我在写通用库时倾向后者写教学代码时用前者因为可读性更好。// 向上调整0 基大顶堆 void siftUp(vectorint h, int i) { while (i 0) { int p (i - 1) 1; if (h[i] h[p]) break; // 偏序已满足提前退出 swap(h[i], h[p]); i p; } }注意那个break的位置。它放在交换之前意味着一旦发现不需要交换就立刻停。这个提前退出不是可有可无的优化而是正确性的保证之一——如果写成先交换再判断逻辑上也能跑通但会多一次无谓的交换而且在某些变体比如带自定义比较器的堆里容易写错比较方向。3.2 向上调整的复杂度与一个反直觉的事实单次插入的向上调整最坏情况是从叶子一路走到根路径长度是树高也就是 O(log n)。这个结论大家都知道。但有个反直觉的事实插入操作的平均调整次数远小于 log n。因为新元素随机插入时它只需要上浮到比父节点小的位置就停了期望上浮层数是常数级别准确说是约 1.6 层左右与堆大小关系不大。这也是为什么堆的插入在实际使用中非常快比理论最坏情况给人的印象要快得多。这个性质对工程选型有实际意义如果你的场景是大量插入、偶尔取极值堆是非常合适的选择插入的摊还成本很低。反过来如果场景是频繁删除任意元素堆就不合适了因为堆只擅长处理堆顶删除中间元素需要先定位再调整定位本身是 O(n) 的。实操心得向上调整函数一定要单独抽出来不要和插入逻辑揉在一起。因为建堆、修改堆中某元素的值比如 Dijkstra 里的松弛操作都会复用它。抽出来之后插入就是push_back siftUp(size-1)两行修改元素就是改值 siftUp 或 siftDown代码复用率极高。4. 向下调整删除堆顶与建堆的共同核心4.1 删除堆顶的标准流程删除堆顶是堆最核心的操作也是细节最多的地方。流程是把堆顶元素和数组末尾元素交换然后弹出末尾此时堆顶位置放的是原来的末尾元素再对堆顶执行向下调整。为什么这么做因为直接删堆顶会让根空出来而完全二叉树不能有空位把末尾元素挪到根结构性质保住了只需要修复偏序。向下调整的逻辑从当前节点 i 开始找出它和左右孩子中最优先的那个大顶堆就是最大的如果这个最优先的不是 i 自己就交换然后 i 移到那个孩子的位置继续。循环终止条件是i 已经是叶子没有孩子或者 i 已经比两个孩子都优先。// 向下调整0 基大顶堆n 是当前堆大小 void siftDown(vectorint h, int i, int n) { while (true) { int l 2 * i 1; int r 2 * i 2; int largest i; if (l n h[l] h[largest]) largest l; if (r n h[r] h[largest]) largest r; if (largest i) break; // 已满足偏序 swap(h[i], h[largest]); i largest; } }这段代码里有三个边界判断每一个都不能省l n保证左孩子存在r n保证右孩子存在largest i保证偏序已满足。我见过有人把r n写成r n数组越界读一个垃圾值然后在大顶堆里这个垃圾值如果恰好很大就会把错误元素换上去表现为偶尔排序结果不对极难排查。4.2 为什么向下调整比向上调整更容易写错向上调整只需要看一个父节点向下调整要看两个孩子还要在三个候选里选最优先的。这个三选一的结构是错误高发区。常见的写法错误有这么几类第一类是比较方向写反。大顶堆里应该是孩子比当前大就换有人写成孩子比当前小就换结果建出来是小顶堆和预期相反。这种错误在测试时如果只测了取最大值会立刻暴露但如果测试用例恰好是递增序列可能碰巧通过埋下隐患。第二类是只比较了一个孩子。比如只判断左孩子忽略右孩子那么当右孩子更大时就不会交换堆性质被破坏。这种 bug 在随机数据下有一定概率触发但如果测试数据规模小可能一直不触发。第三类是交换后忘记更新 i。交换完 largest 位置的值变了但循环变量 i 没跟着走导致死循环或者调整不到位。这个错误编译器不会报运行时表现为卡死或者结果错误。第四类是n 参数传错。向下调整需要知道当前堆的有效大小因为建堆过程中堆是逐步长大的堆排序过程中堆是逐步缩小的。如果函数内部用 h.size() 而不是传入的 n建堆和堆排序都会出错。这就是为什么 siftDown 的签名里必须显式带 n。注意siftDown 的 n 参数是当前有效堆大小不是数组容量。建堆时 n 固定为数组长度堆排序时 n 从 length 递减到 1。把这两个概念混在一起是堆排序写错的头号原因。4.3 向下调整的复杂度分析单次向下调整最坏情况是从根走到叶子路径长度是树高 O(log n)。但和向上调整不同向下调整的平均代价更接近最坏情况因为从根出发的元素通常需要走到底部才能找到合适位置。这个差异在分析建堆复杂度时非常关键下面马上会用到。5. 建堆为什么从后往前是 O(n) 而不是 O(n log n)5.1 两种建堆思路的对比建堆有两种做法。第一种是逐个插入从空堆开始每次 push 一个元素调用 siftUp。n 个元素每次 O(log n)总复杂度 O(n log n)。第二种是原地建堆把整个数组当成一棵完全二叉树从最后一个非叶子节点开始倒着对每个节点执行 siftDown总复杂度 O(n)。很多人第一次看到 O(n) 的结论会怀疑每个节点都做一次 siftDown单次最坏 O(log n)n 个节点怎么就不是 O(n log n) 了关键在于每个节点实际走的层数不一样。树底部的节点多但它们几乎不用调整叶子直接跳过倒数第二层最多走一层树顶部的节点少但它们要走很多层。把每个节点的调整代价按层数加权求和得到的是一个收敛的级数最终是 O(n)。具体算一下高度为 h 的节点大约有 n/2^(h1) 个每个最多调整 h 层总代价是 Σ h * n/2^(h1)这个级数的和是 O(n)。直观理解就是绝大多数节点在底部调整代价极低少数在顶部的节点虽然代价高但数量太少拉不动总量。5.2 建堆的起始下标与循环方向0 基下最后一个非叶子节点下标是 n/2 - 1。建堆循环从它开始递减到 0对每个 i 调用 siftDown(h, i, n)。注意这里的 n 是固定的数组长度因为建堆过程中整个数组都是堆的一部分不存在堆在缩小的情况。void buildHeap(vectorint h) { int n h.size(); for (int i n / 2 - 1; i 0; --i) { siftDown(h, i, n); } }这个循环的边界有两个坑。第一个是起始下标n/2 - 1 在 n0 或 n1 时会得到 -1 或 -1循环条件 i 0 直接不进入正确空堆和单元素堆本来就是堆。但如果有人写成 n/2n1 时起始是 0会对唯一的根做一次 siftDown虽然不出错但多余n2 时起始是 1会从下标 1 开始漏掉了下标 0 的根——而根恰恰是最需要调整的建堆结果直接错。第二个是循环变量类型。如果 i 声明成无符号类型size_ti 0 永远为真循环会下溢成巨大值然后越界崩溃。这是 C/C 里非常经典的坑堆的建堆循环是重灾区。解决办法要么用有符号 int要么把循环写成for (int i n/2 - 1; i 0; --i)并确保 n 不会超过 int 范围。实操心得建堆的循环我习惯写成for (int i (n 1) - 1; i 0; --i)用位运算代替除法同时明确用 int。如果项目里数组可能超过 20 亿元素几乎不可能再考虑用 ptrdiff_t。这个写法我用了很多年没出过问题。5.3 建堆过程中一个容易被忽略的细节建堆时当我们处理下标 i 的节点它的左右子树已经是合法的堆了因为我们是倒着处理的孩子下标比 i 大早就处理过了。这个前提是 siftDown 能正确工作的基础——siftDown 假设除了当前节点其余部分都满足堆性质然后通过一次下沉修复当前节点。如果循环方向搞反了从 0 开始正着处理那么处理根的时候它的子树还没被整理过siftDown 的前提不成立结果就是错的。这个倒序处理保证子树已就绪的思路和动态规划里从后往前推的思想是同构的。理解了这个不变式你就不会再把建堆循环方向记错了。6. 堆排序在堆上做原地排序的边界艺术6.1 堆排序的完整流程堆排序分两大步先建堆然后反复取堆顶放到末尾、缩小堆、恢复堆性质。以大顶堆升序排序为例建好大顶堆后堆顶是全局最大值把它和数组末尾交换最大值就归位到了最终位置然后堆的有效大小减一末尾那个位置不再属于堆对新的堆顶执行 siftDown 恢复性质重复这个过程直到堆大小为 1。void heapSort(vectorint h) { buildHeap(h); for (int n h.size(); n 1; --n) { swap(h[0], h[n - 1]); // 堆顶归位到末尾 siftDown(h, 0, n - 1); // 在缩小的堆上恢复性质 } }6.2 循环边界为什么是 n 1这个循环条件是最容易写错的地方之一。为什么是 n 1 而不是 n 0因为当堆大小为 1 时堆里只剩一个元素它自然就在正确位置不需要再交换和调整。如果写成 n 0当 n1 时会执行 swap(h[0], h[0])自己和自己换无害然后 siftDown(h, 0, 0)——此时 n-10siftDown 里 l1 不满足 l0直接返回也无害。所以 n 0 其实也能跑通但多做了一次无意义的迭代。真正会出错的是写成 n 1 配合错误的 siftDown 参数或者在 siftDown 里传 n 而不是 n-1。传参这里要特别小心交换之后堆的有效范围是 [0, n-2]共 n-1 个元素所以 siftDown 的第三个参数应该是 n-1。如果传成 n就会把已经归位的末尾元素又拉回堆里参与比较导致排序结果错误。这个错误非常隐蔽因为数组看起来差不多有序只是个别位置不对。6.3 升序用大顶堆还是小顶堆这是个经典问题。结论是升序排序用大顶堆。原因在于堆排序的归位动作是把堆顶放到当前堆的末尾。大顶堆的堆顶是最大值放到末尾正好是升序序列的最后一个位置然后堆缩小下一个最大值放到倒数第二个位置依次类推。如果用小顶堆做升序堆顶是最小值放到末尾就变成了降序还得再反转一次多此一举。这个选择背后其实是一个目标位置与极值方向匹配的原则你要把极值放到哪一端就用哪种堆。升序要把最大值往右端放所以用大顶堆降序要把最小值往右端放所以用小顶堆。记住这个原则就不用死记了。6.4 堆排序的稳定性与工程取舍堆排序是不稳定的。交换堆顶和末尾元素这个动作会打乱相同值元素的相对顺序。比如数组里有两个 5一个在前一个在后排序后它们的相对位置可能颠倒。如果业务要求稳定排序堆排序就不合适得用归并排序或者稳定的排序库函数。那堆排序的优势在哪空间复杂度 O(1)原地排序不需要额外数组。归并排序要 O(n) 辅助空间快速排序虽然平均也是 O(1) 额外空间但递归栈有开销。所以在内存极度受限、又不需要稳定性的场景堆排序有它的位置。不过说实话实际工程里纯堆排序用得不多因为它的缓存局部性不如快速排序siftDown 的访问模式是跳跃的常数因子偏大。堆更多是以优先队列的形式出现在算法里而不是作为通用排序手段。注意很多教材说堆排序最坏 O(n log n)优于快速排序的最坏 O(n²)。这话没错但工程上快速排序的平均性能更好而且现代快速排序用三数取中、小数组插排等优化后最坏情况很难触发。选排序算法要看具体场景不要唯复杂度论。7. 常见问题与排查技巧实录7.1 堆相关 bug 的排查速查表下面这张表是我这些年调试堆代码时积累的高频问题清单按现象→可能原因→排查方法组织遇到问题可以直接对照。现象可能原因排查方法取出的极值偶尔不对siftDown 的 n 参数传错把已归位元素拉回堆打印每次 siftDown 的区间确认右边界建堆后根不是极值建堆起始下标错漏调了根检查循环起点是否为 n/2-1程序卡死siftDown 交换后没更新 i或循环条件写反在循环里打印 i看是否单调移动数组越界崩溃孩子下标判断用了 而非 检查 ln 和 rn 两处排序结果整体反了升序用了小顶堆确认堆类型与目标顺序匹配小数据对、大数据错下标计算在边界值上出错用 n0,1,2,3 逐个手推无符号循环下溢循环变量用了 size_t 且条件 i0改用有符号 int7.2 三个我踩过的真实坑第一个坑是建堆和堆排序共用 siftDown 但 n 语义不同。建堆时 n 是数组全长且不变堆排序时 n 是递减的。我早期图省事让 siftDown 内部用 h.size() 当 n结果堆排序时已经归位的元素又被拉回来比较排序结果在数据量大时出现局部乱序。后来强制 siftDown 必须显式传 n这个类问题再没出现过。第二个坑是自定义比较器时的方向混乱。有次做一个任务调度器用堆按优先级排序比较器写的是优先级高的在前但 siftDown 里用的是大于号两者叠加后方向反了两次结果居然看起来对直到某个边界任务被错误调度才发现。教训是比较器和调整逻辑的方向必须在一处统一最好把比较抽成一个函数siftUp 和 siftDown 都调它避免两处各写一套。第三个坑是修改堆中元素的值之后忘记调整。在 Dijkstra 这类算法里我们会更新某个节点的距离值如果这个节点在堆里更新后必须重新调整它的位置变小了就 siftUp变大了就 siftDown。我见过有实现只更新了值没调整堆性质被破坏最短路结果偏大。标准库的优先队列不支持修改堆中元素所以要么用插入新值懒删除的技巧要么自己实现带位置索引的堆。7.3 懒删除技巧标准库优先队列的实战用法标准库的优先队列通常只提供 push、top、pop不支持删除任意元素。实际业务里经常需要删除某个已入队的元素怎么办常用技巧是懒删除不真正删除而是额外维护一个已删除标记集合每次取堆顶时检查堆顶是否已被标记删除如果是就 pop 掉再取下一个。这个技巧的关键是保证标记集合和堆的同步。比如任务调度场景任务被取消时把任务 ID 加入取消集合取堆顶时循环检查只要堆顶任务的 ID 在取消集合里就 pop 并继续。这样删除是 O(1) 标记摊还到每次取堆顶时清理整体复杂度仍然是 O(log n) 级别。缺点是堆里可能堆积大量已删除元素内存占用偏高适合删除操作不算太密集的场景。实操心得懒删除配合版本号比配合ID 集合更稳。每个元素入堆时带一个版本号元素被更新时版本号加一堆里存的是旧版本。取堆顶时比对当前版本号和堆里版本号不一致就丢弃。这样连删除标记集合都不用维护逻辑更干净也不怕 ID 重复的问题。8. 从堆到优先队列工程化的最后一公里8.1 封装优先队列时该暴露什么接口手写堆的最终目的多半是封装成一个优先队列供业务使用。接口设计上有几个决策点。首先是是否暴露底层数组——不建议暴露因为外部一旦直接改数组堆性质就破坏了后续所有操作都不可信。其次是是否支持自定义比较器——建议支持用模板参数或函数对象传入这样同一个堆实现能同时服务大顶堆和小顶堆不用写两份。最后是是否支持修改元素——如果业务需要就得在元素里存位置索引并在每次交换时同步更新索引这是带索引堆的标准做法代价是每次交换多两次赋值。带索引堆的实现要点维护一个 pos 数组pos[元素ID] 该元素在堆数组中的下标。每次 swap 时同步交换 pos 里的两个值。这样给定元素 ID 就能 O(1) 定位到它在堆里的位置然后 O(log n) 调整。Dijkstra、Prim 这类算法用带索引堆能把复杂度里的 log 因子压得更实。8.2 堆的适用边界什么时候不该用堆堆不是万能的。它的强项是动态维护极值弱项是查询任意元素和有序遍历。如果你的需求是取前 k 大堆很合适维护大小为 k 的小顶堆遍历一遍即可如果需求是全部排序堆排序不如快速排序实用如果需求是频繁查询中位数单个堆不够得用对顶堆一个大顶堆存较小的一半一个小顶堆存较大的一半保持两边大小平衡。对顶堆是堆的一个漂亮应用维护细节在于平衡每次插入后检查两个堆的大小差超过 1 就把多的那个堆的堆顶挪到另一个堆。取中位数时看总元素个数的奇偶奇数取元素多的那个堆的堆顶偶数取两个堆顶的平均。这个结构在流式数据处理里很常见值得单独练一遍。我在实际项目里用堆最多的场景是定时任务调度和带优先级的消息处理这两个场景的共同点是不断有新任务进来、每次只关心最紧急的那个。堆在这个模式下的表现非常稳插入和取极值都是对数级内存也紧凑。唯一要留心的是前面说的懒删除导致的内存膨胀定时任务如果取消率很高得定期重建堆来回收空间。8.3 一个值得反复练手的练习路径想把堆真正写扎实我建议按这个顺序练第一步手写 siftUp 和 siftDown用 n0 到 5 的小数组逐个手推验证第二步写建堆验证建堆后数组满足堆性质写个检查函数遍历一遍第三步写堆排序和标准库排序结果对比第四步封装成模板优先队列支持自定义比较器第五步实现带索引的堆跑一遍 Dijkstra 验证。这五步走完堆的维护细节基本就刻进肌肉记忆了。每一步都要写测试尤其是边界测试空堆、单元素、两元素、全部相等、严格递增、严格递减。这六种输入能覆盖绝大多数边界 bug。我见过太多人只测随机数据随机数据反而最难触发边界问题因为边界情况在随机分布里概率极低。最后分享一个检查堆性质的小函数写完堆之后随手跑一下比肉眼调试高效得多bool isHeap(const vectorint h) { int n h.size(); for (int i 0; i n; i) { int l 2 * i 1, r 2 * i 2; if (l n h[l] h[i]) return false; if (r n h[r] h[i]) return false; } return true; }这个函数 O(n) 遍历一遍任何一次调整之后都可以调它验证。养成改完就验的习惯堆的 bug 基本活不过五分钟。
阅读完成 · 觉得有帮助？
