每次讲到堆这一章总有学生举手问“老师这东西不就是个优先队列吗C 里有现成的priority_queueJava 里有PriorityQueue笔试的时候直接调 API 不就行了为什么还要自己手写一遍”这个问题问得特别好因为它背后藏着一个真相堆的价值不在于“能不能用”而在于“懂它为什么快”。堆排序能在任何输入下都保持 O(n log n) 的时间复杂度TOP-K 问题在数据量过亿、内存装不下的时候只有堆能扛住。我跟学生说调 API 的人看到的是接口手写堆的人看到的是数据流。这篇博文就来做一次完整拆解——从完全二叉树为什么能“压扁”进数组到向上调整和向下调整这两个核心函数的取舍再到堆排序和 TOP-K 的代码级走读最后聊聊我在教学和刷题中见惯了的高频翻车现场。不管你是刚接触数据结构的初学者还是准备面试想快速捡起堆的老手这篇内容都值得花半小时看完。1. 堆的底层真相一棵被“压扁”成数组的完全二叉树很多人第一次接触堆看到的就是一个数组[10, 7, 8, 3, 4, 6, 5]。光看数组看不出任何规律但如果把它画成一棵二叉树一切就清晰了——这棵树就是堆的真身。1.1 完全二叉树堆能存进数组的“入场券”不是所有二叉树都能用数组存得这么舒服堆要求的是一种特殊形态完全二叉树。定义听起来有点绕——除了最后一层其他层的节点数都必须填满而且最后一层的节点必须从左到右连续排列中间不能有空位。为什么要这么苛刻因为“连续”两个字是关键。一旦树是连续的就可以对每个节点编号根节点是 0 号然后从左到右、从上到下依次编号。于是就有了数据结构教科书里那三句被念叨了无数遍的下标公式第 i 个节点的左孩子2 * i 1第 i 个节点的右孩子2 * i 2第 i 个节点的父节点(i - 1) / 2打个比方这就好比电影院座位的连续编号。一排座位坐得整整齐齐你只要知道自己的座位号立刻能算出旁边是谁。但如果中间空了一格不是完全二叉树编号就会断档数组里就得留空洞存储密度就下来了。我这几年带学生做课程设计见过不少人试图用链表实现堆。技术上不是不行但我都会劝他们换回数组理由有两条。第一链式存储每个节点要多存两个指针在堆这种节点数以万计的场景下内存浪费是实打实的。第二数组元素在内存中是连续存放的CPU 缓存友好访问相邻元素的速度比链式结构快一个量级。堆排序之所以在工程里还有一席之地数组存储的局部性功不可没。1.2 大根堆与小根堆堆序性质才是灵魂数组形态和下标公式只是容器堆的“灵魂”是一条叫堆序性质的规则。规则很简单只有一句话大根堆每个节点的值都大于等于它的左右孩子堆顶是最大值。小根堆每个节点的值都小于等于它的左右孩子堆顶是最小值。注意措辞——“大于等于它的孩子”而不是“大于等于所有后代”。这意味着堆只保证父子之间存在大小关系兄弟之间、叔侄之间没有任何约束。所以堆是一个典型的“局部有序”结构你只知道堆顶一定是全局最大或最小剩下的元素谁大谁小你一概不清楚。这个特性常常让刚入门的同学踩坑。有人拿到一个大根堆以为第二大的数一定在堆顶的某个孩子里进而以为可以像二分查找一样在堆里“搜”某个值——这是错的。查找不是堆的强项堆的强项是“极值进出”。如果你需要既能快速查找又能快速取极值那应该去看二叉搜索树或者平衡树而不是堆。1.3 用比赛淘汰赛来理解堆的运作方式我给初学者做类比时最喜欢用的是单败淘汰赛。16 个人打比赛冠军只需要打 4 场但谁能告诉我亚军是谁亚军不一定是在决赛里输给冠军的那个人——他可能在半决赛就被冠军淘汰了。堆就是这样一棵“比赛树”堆顶是冠军但第二名藏在某个子树的深处毫无规律可循。这个类比还能延伸到另一个结论找最大值很快看堆顶O(1)但找到之后要把冠军“请出”赛场让其他人重新角逐这个过程就需要让路径上的选手重新比一轮这就是后面要讲的“向下调整”代价是 O(log n)。2. 堆的两个核心操作向上调整与向下调整到底该怎么选堆的所有操作本质上都是围绕两个函数转的AdjustUp向上调整和AdjustDown向下调整。很多人代码背得滚瓜烂熟但一到“该用哪个”就发懵。这一节我用最直白的方式把这两个函数讲透。2.1 shift_up新元素的自下而上“晋升”之路想象大根堆里现在有 5 个元素你要插入一个新值。数组层面很简单把新值放到size位置也就是数组末尾然后size。但插完之后堆序性质可能被破坏了——新值可能比它的父节点还大。怎么办让它一路“晋升”和父节点比大小大了就交换直到它不再大于父节点为止。void Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } // 大根堆向上调整 void AdjustUp(int* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { Swap(a[child], a[parent]); child parent; parent (child - 1) / 2; } else { break; } } }这里有个细节值得停下来看一眼while (child 0)是循环的继续条件。一旦新元素晋升到根节点child变成 0循环自然结束。而循环体里的break同样关键——如果新元素已经不比父节点大了说明堆序性质恢复就没必要再往上走了。一个常见的小聪明是既然最后都要到根能不能把循环走到child 0为止省掉break我在阅卷时确实见过这种写法功能上没错但白白多做几次比较性能上有损耗。更重要的是这种写法会让代码逻辑变模糊——你明明可以在恰当的位置停下来为什么要硬撑到顶2.2 shift_down堆顶被拿走后的“纠偏”过程删除堆顶也就是取出最大值是堆的招牌操作。算法不长思路是三步先把堆顶和最后一个元素交换然后size--把原堆顶彻底扔掉最后从新的堆顶开始向下调整。为什么不能直接把根删掉再把数组往前挪那样会产生两个问题一是数组整体前移是 O(n) 操作太慢二是挪完之后树的结构就不是完全二叉树了。先换到末尾再删完全二叉树的形态始终保持不变。向下的“纠偏”逻辑正好和向上相反。当前节点如果是“小个子”它就要不断和两个孩子比较选出较大的孩子如果孩子更大就交换然后继续往下走。// 大根堆向下调整n 是堆的有效元素个数 void AdjustDown(int* a, int n, int parent) { int child parent * 2 1; // 默认先看左孩子 while (child n) { // 如果右孩子存在且比左孩子大就把 child 指向右孩子 if (child 1 n a[child 1] a[child]) { child child 1; } // 此时 child 已经是两个孩子里较大的那个 if (a[child] a[parent]) { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } }请务必重视“选出较大的孩子”这一步。如果你随随便便拿左孩子跟父节点比交换之后左孩子确实满足了堆序但右孩子可能还比父节点大堆序性质仍然不成立。只有把两个孩子中较大的那个换上来才能保证交换后父节点同时“压得住”两个孩子。2.3 一张表搞清两个调整函数的适用场景很多初学者把AdjustUp和AdjustDown当成“功能相似的两个函数”用的时候靠猜。我用一张表帮学生建立条件反射操作场景用什么函数起始位置原因插入一个新元素AdjustUp数组末尾新元素位置新元素唯一可能破坏堆序的方向是“向上”删除堆顶AdjustDown堆顶交换后的根换上去的元素偏小需要“下沉”替换堆顶TOP-K 常用AdjustDown堆顶同删除堆顶替换后堆顶可能偏小修改某个元素使其变大AdjustUp该元素位置值变大后可能超过父节点修改某个元素使其变小AdjustDown该元素位置值变小后可能小于孩子从一个无序数组建堆AdjustDown最后一个非叶节点下节的“向下调整建堆法”判断标准其实就一句话元素值是“变大了”还是“变小了”以及它相对于父节点还是孩子节点违约。向上调整解决的永远是“比爸爸大”的问题向下调整解决的永远是“比儿子小”的问题。这里顺便提醒一句替换堆顶时不要写成“先 pop 再 push”。这两个操作合在一起需要两次 O(log n) 调整而直接heap[0] 新值; AdjustDown(...)只需要一次。在 TOP-K 这种要跑 n 次的场景里一次和两次的差距就是成倍的耗时。3. 建堆的效率账本O(n) 是怎么从 O(nlogn) 里省出来的建堆是堆这章第一个“反直觉”的知识点。我第一次学的时候也觉得古怪往堆里插入一个元素是 O(log n)插入 n 个元素理应是 O(n log n)为什么教科书上白纸黑字写着建堆可以做到 O(n)两种建堆方法咱们逐一算账。3.1 方法一从空堆开始逐个插入思路很朴素初始化为空堆然后循环 n 次每次调AdjustUp。void HeapCreateByInsert(int* a, int n) { // 假设 a 的空间足够从空堆开始 int size 0; for (int i 0; i n; i) { a[size] a[i]; // 实际工程中通常先拷贝到新数组 size; AdjustUp(a, size - 1); } }每次插入的代价是 O(log n)总代价就是 O(n log n)。这个复杂度没错但不理想。当 n 是 100 万时n log n 和 n 的差距大约是 20 倍在大数据场景下这是不可接受的。3.2 方法二从最后一个非叶节点向下调整第二个方法的精髓是“自底向上调整”。你先看一眼数组把它当成一棵完全二叉树这不需要任何额外存储下标公式就是映射关系然后用一个循环从最后一个非叶节点开始逐个往前调用AdjustDown。关键问题来了最后一个非叶节点在哪个位置答案(n - 2) / 2。推导非常简单——最后一个节点数组末尾的下标是n - 1它的父节点就是((n - 1) - 1) / 2 (n - 2) / 2。既然它是最后一个节点的爸爸而完全二叉树的节点又是连续编号的那么下标比它大的节点全都得叫它一声“父辈”或者干脆是叶子没有孩子可调了。void HeapBuild(int* a, int n) { for (int i (n - 2) / 2; i 0; i--) { AdjustDown(a, n, i); } }就这么几行复杂度却是 O(n)。我第一次推完这个结论时觉得数学真奇妙。3.3 复杂度推导等比数列求和的艺术为什么是 O(n)关键在“大部分节点都离叶子很近”。我们从下往上给每层算工作量叶子层倒数第 0 层大约 n/2 个节点每个节点不需要移动工作量 0。倒数第 1 层大约 n/4 个节点每个节点最多向下移动 1 次工作量 n/4。倒数第 2 层大约 n/8 个节点每个节点最多向下移动 2 次工作量 n/4。倒数第 k 层大约 n/2^(k1) 个节点每个节点最多移动 k 次工作量 n·k / 2^(k1)。把各层工作量加起来得到的总工作量 T 是T n/4 2·(n/8) 3·(n/16) … (n/2) · (1/2 2/4 3/8 …)括号里的级数收敛于 2这是经典的等比-等差混合级数所以 T ≈ n即 O(n)。这个推导的精髓在于越靠近根节点数量越少但移动距离越长越靠近叶子节点数量越多但移动距离越短。两头一抵消总和被控制在了线性级别。上课时我跟学生说叶子节点多到数不清但人家根本不用动真正需要“长途跋涉”的只有根附近那少数几个节点所以这个账怎么算都不会亏。条件反射式的提醒初始建堆务必用向下调整插入建堆只在需要维护动态数据流时才合理。4. 堆排序的临门一脚从堆顶到有序序列的完整走读堆排序是堆这章最“出圈”的知识点面试手撕、期末考试、课程设计全都绕不开它。它的思路其实只有两步但细节处全是坑。4.1 排序核心思路建大堆 不断交换堆顶先明确一个原则升序排序建大根堆降序排序建小根堆。很多人习惯性地以为“升序嘛先拿最小值”于是建了小根堆结果发现每次取堆顶最小值得到的序列确实是升序但需要一个额外的输出数组空间复杂度变成 O(n)。正确的原地做法很巧妙建大根堆堆顶是最大值让它跟数组末尾元素交换然后堆的规模减一再对新的堆顶做AdjustDown。这样最大值就被“钉死”在末尾了下一次循环处理的就是前面 n-1 个元素。不断重复最小值最后自然落在下标 0 处数组整体就是升序。4.2 代码走读HeapSort 的两段式实现void HeapSort(int* a, int n) { // 第一段建大根堆 for (int i (n - 2) / 2; i 0; i--) { AdjustDown(a, n, i); } // 第二段把堆顶“沉”到末尾缩小堆范围继续调整 for (int end n - 1; end 0; end--) { Swap(a[0], a[end]); // 当前最大值归位 AdjustDown(a, end, 0); // 注意堆的有效长度是 end不是 n } }第二段循环里那个AdjustDown(a, end, 0)是整段代码最容易写错的地方。end传进去的是“堆的有效长度”因为最后一个元素已经归位不能再参与堆调整了。如果用n做长度已经排好的元素又会被翻上来排序直接前功尽弃。这个 bug 我在学生作业里见过不下十次。来走一个完整的小例子感受一下。数组[3, 5, 5]两个 5 我用 5ₐ 和 5ᵦ 区分。建堆(3-2)/2 0对下标 0 执行AdjustDown。左孩子是下标 1 的 5ₐ右孩子是下标 2 的 5ᵦ右孩子不比左孩子大所以选中左孩子。3 和 5ₐ 交换得到[5ₐ, 3, 5ᵦ]。end 2交换堆顶 5ₐ 和末尾 5ᵦ得到[5ᵦ, 3, 5ₐ]对前 2 个元素调整3 和 5ᵦ 不动因为 5ᵦ 已经是堆顶。end 1交换 5ᵦ 和 3得到[3, 5ᵦ, 5ₐ]调整结束。你看初始时 5ₐ 在 5ᵦ 前面排序后变成了 5ᵦ 在前、5ₐ 在后两个相等元素的相对顺序颠倒了。这说明堆排序是不稳定的。4.3 稳定性检查为什么堆排是“不稳”的先解释什么叫稳定排序如果两个相等的元素在排序前是 A 在前、B 在后排序后依然 A 在前、B 在后那这个排序就是稳定的。插入排序、归并排序是稳定的选择排序、快排、堆排都是不稳定的。堆排序不稳定的根源在“远距离交换”。堆排序的交换不是相邻交换而是堆顶和末尾跨越整个数组长度的交换这种大跨度交换很容易把相等元素的相对顺序打乱。我在上面那个[3, 5ₐ, 5ᵦ]的例子就完美展示了这一点。如果你要排的数据里包含“关键字相同的记录”而记录之间还有次要字段需要保持原有先后顺序那堆排序就不是首选。4.4 堆排 vs 快排什么时候选谁很多人问既然快排平均也是 O(n log n)而且常数更小为什么还要学堆排我的答案有三个。第一快排存在最坏情况 O(n²)虽然可以通过随机化、三数取中等手段缓解但堆排序是铁打不动的 O(n log n)任何输入都不例外。对实时性要求高、不可接受“最坏情况”的场合堆排更让人安心。第二堆排序是原地排序不需要额外数组空间复杂度 O(1)这比归并排序的 O(n) 空间友好得多。第三记住了前面那句“升序建大堆、降序建小堆”你在面试时能顺手写出一个稳定的 O(n log n) 排序算法这本身就是一种兜底能力。代价也很明显堆排序的常数因子比快速排序大而且它访问数组的模式是“跳来跳去”的缓存局部性远不如从头到尾扫描的快排和归并。所以工程实践中通用排序库几乎都用快排或混合排序堆排序更适合“需要在动态变化的集合里反复取极值”的场景而不是纯粹的排序。5. TOP-K在 1 亿个数里挑前 100 大的最优姿势TOP-K 是堆在工程里最高光的应用。问题描述很朴素从 n 个数里找出最大的 K 个数或者最小的 K 个数。数据量小的时候随便怎么做都对但一旦 n 变成千万、亿级别K 只有几十、几百事情就没那么简单了。5.1 先排除两个“看着很香”的错误方案方案一全部排序取前 K 个。时间复杂度 O(n log n)简单粗暴。问题是你为了找 100 个数把 1 亿个数全排了这就像为了找一个掉在地上的针把整座仓库的地板都掀了。而且如果数据是流式的——比如它来自一个网络接口一条一条到达总量未知——你根本没法“全部排序”。方案二冒泡/选择排序只走 K 趟。每趟找出一个最大值K 趟的复杂度是 O(nK)。如果 K 很小比如 K10这个方案勉强能用但 K1000、n1 亿的时候1 亿乘以 1000 等于 100 亿次操作照样扛不住。5.2 小根堆解法为什么是它而不是大根堆正确解法是维护一个容量为 K 的小根堆堆里装的是“目前见过的最大 K 个数”。然后遍历一遍数据对每个新元素 x如果 x 小于等于堆顶说明它连当前第 K 大的门槛都够不着直接忽略。如果 x 大于堆顶说明它应该挤进前 K。把堆顶替换成 x然后向下调整。为什么是小根堆因为堆顶是这 K 个数里最小的那个也就是“前 K 大的门槛”。新元素只要比门槛高就踢掉门槛、自己进门。如果用了大根堆堆顶固然是最大但你根本不知道这 K 个数里哪个最小也就没法判断新元素能否入场。所以说“找前 K 大”用的是小根堆“找前 K 小”用的是大根堆这个反直觉的结论一定要背下来。还有一层隐性的好处全程只需要存 K 个元素。1 亿个数不需要全部读进内存可以一条一条处理天然适合数据流。5.3 代码实现与复杂度核算// 找出数组 a 中前 K 大的数minHeap 是大小为 k 的输出数组 void TopK(int* a, int n, int k, int* minHeap) { // 先用前 k 个元素建小根堆 for (int i 0; i k; i) { minHeap[i] a[i]; } for (int i (k - 2) / 2; i 0; i--) { AdjustDown(minHeap, k, i); } // 遍历剩余元素更新堆 for (int i k; i n; i) { if (a[i] minHeap[0]) // 注意小根堆的堆顶是最小值 { minHeap[0] a[i]; AdjustDown(minHeap, k, 0); } } // 结束后 minHeap 里就是前 K 大的数但内部不保证有序 }复杂度核算分两部分建堆 O(k)遍历比较 n 次其中最多 n 次会触发AdjustDown每次 O(log k)。所以总复杂度是 O(n log k)。当 K 远小于 n 时log k 是个很小的常数整体上相当于线性扫描了一遍数据这才是 TOP-K 真正迷人的地方。这里有个工程细节minHeap里的元素最终是无序的。如果后续要按从大到小展示可以先对这 K 个元素排一下序反正 K 很小排序代价可以忽略。5.4 扩展变式第 K 大、数据流与动态 TOP-KTOP-K 的变式在面试里极其常见但核心解法不变。找“第 K 大的数”和 TOP-K 一模一样维护小根堆结束后堆顶就是第 K 大的数。如果你只需要知道第 K 大不需要把前 K 个全部输出那么堆这种方案的内存和速度优势更明显。数据流动态 TOP-K堆的插入和删除都是 O(log K)新数据到了就尝试“踢掉门槛”因此堆能天然支持动态变化的 TOP-K。换成排序方案每来一条数据就全排一次复杂度直接爆炸。还有一类变式是“窗口内 TOP-K”滑动窗口里的最大值问题那是单调队列的主场跟堆是两套完全不同的思路。如果你把窗口内所有数放进堆删除窗口左端元素会很痛苦因为堆不擅长“定点删除”。这个题我建议单独学单调队列别硬用堆。6. 初学堆的常见翻车现场边界、递归与调试心得代码本身不复杂但初学者写堆翻车率极高。我把这几年见到的典型错误集中盘一盘每一个都是血泪教训。6.1 下标从 0 还是从 1统一标准赢一半教科书上有些版本用下标从 1 开始父节点是i/2左孩子是2*i右孩子是2*i1。而 C 语言的数组天然从 0 开始。混用两套公式是 off-by-one 错误的重灾区。我自己的习惯是代码里统一用 0 下标体系公式写死在注释里。左孩子2*i1、右孩子2*i2、父节点(i-1)/2、最后一个非叶节点(n-2)/2。这四个公式我建议初学者抄在纸上调试的时候对着看。一旦开始用某个体系不要在代码里穿插另一套否则等着你的就是野指针和随机值。6.2 向下调整的两个边界条件child 越界和 child1 越界AdjustDown里有两个边界条件是“约定俗成的考点”。第一while (child n)保证左孩子不越界。这个条件漏写了拿a[child]的时候就可能读到堆范围之外的内存。第二比较两个孩子时必须加child 1 n的判断因为右孩子可能不存在——这对应着“最后一层最右侧的节点只有一个左孩子”的情况。if (child 1 n a[child 1] a[child]) { child child 1; }注意这里的短路求值child 1 n为假时后面的a[child 1] a[child]根本不会执行所以就算child 1越界也只是“还没读”不会真正访问到非法内存。但这只是侥幸不要依赖它判断条件必须写上。6.3 循环还是递归小心“栈溢出”才是真正的堆栈问题AdjustDown可以写成递归逻辑上更“优雅”但我建议初学阶段一律用循环。理由很简单递归需要函数调用栈虽然AdjustDown的递归深度只有 O(log n)在堆这种平衡结构里不太可能真栈溢出但循环版本没有这个额外负担也更容易肉眼检查边界。顺便说一个被无数人混淆的点数据结构里的“堆”和程序运行时内存里的“堆栈”是两个完全不同的概念。前者是我们这章讲的树形数据结构后者是操作系统给进程分配内存的两种区域——栈存局部变量堆存动态分配的对象。网上搜“堆栈区溢出”“堆空间不足”出来的是内存管理的报错跟本章的堆数据结构没有直接关系。初学者如果被这两个“堆”绕晕记住一个区分方法数据结构堆讨论的是“怎么组织数据”内存堆讨论的是“内存怎么分配”。6.4 调试技巧打印堆 手工走查小样例手写堆出了问题怎么快速定位我的三板斧如下。第一写一个PrintHeap函数直接按数组顺序打印配合“每层换行”的格式化输出一眼看清树结构。堆序性质是否成立视觉检查比单步调试快得多。第二写一个校验函数IsHeapint IsHeap(int* a, int n) { for (int i 1; i n; i) { if (a[(i - 1) / 2] a[i]) // 大根堆要求父 子 { return 0; } } return 1; }把IsHeap插到每次AdjustDown和AdjustUp之后自动检查堆序性质是否被破坏。这是排查“这个元素到底该往上走还是往下走”类问题的最快方式。第三拿长度 5~7 的小数组手工在纸上模拟一遍算法每交换一次就在纸上画一棵树。当年我学堆排序的时候把[4, 3, 6, 2, 1, 5, 7]从头到尾画了整整三遍才真正吃透“堆的有效长度缩小”这件事。这种笨办法的学习效率远高于盯着调试器发呆。6.5 关于封装的一点建议先把裸函数跑通再包装成类很多 C 语言课程要求用结构体封装一个 “Heap” 类型包含a、size、capacity三个字段再写HeapPush、HeapPop、HeapTop这些接口。这是个好练习但我的建议是先写裸的AdjustUp和AdjustDown配一个普通数组做测试确认逻辑没问题后再把它包进结构体里。一次只引入一个“新东西”否则你分不清 bug 是出在核心逻辑还是出在内存管理上。等结构体版本的堆写顺了再回头对比一下标准库的优先队列你会发现原理完全一致push就是先尾插再AdjustUppop就是先交换再AdjustDown。这时候你对优先队列的理解就不再是“调 API”而是“知道它在背后做了什么”。最后再分享一个我的个人习惯每次写完堆相关代码我都会随手拿一个随机数组跑一遍HeapSort然后用IsSorted校验再拿一个小规模 TOP-K 用例验证堆顶是不是正确的第 K 大。数据结构和算法这种东西看十遍不如手写一遍手写一遍不如调试一遍。把这个习惯保持住堆这章你就真正拿下了。