1. 为什么堆和堆总让人分不清先说名字里的坑我第一次学数据结构时最崩溃的地方不是算法本身而是堆这个名字。操作系统课里说堆是动态分配内存的区域JVM调优时说堆外内存C报错说堆已损坏结果数据结构课又冒出来一个堆还是个二叉树。三个堆字说的完全不是一回事。当年我在论坛上看到有人问堆和栈的区别下面的人吵了三百楼——因为有人答内存布局有人答数据结构还有人答的是调用栈。谁都对谁都没对上频道。所以这篇文章开篇第一件事就是把概念边界先画清楚。操作系统/运行时里的堆heap一段用来动态分配内存的区域由malloc、new、GC 等机制管理和数据结构没有直接关系。系统栈stack函数调用时压栈的帧结构先进后出和栈这种数据结构确实同构但它是运行时机制。数据结构里的堆heap一种完全二叉树形态的树形结构满足特定的大小关系约束。本文要讲的就是这个东西。这三个概念共享堆这个词纯属历史遗留习惯没有任何深奥原因。你要是非要找一点共性勉强可以说操作系统里的堆在分配内存时倾向于把碎片化的小块拼成大块和数据结构的堆动态调整优先级的思想有一点点神似但这个类比站不住脚最大的作用就是考试之前别把自己绕晕。数据结构里的堆大多数教材会给出一个定义一棵完全二叉树并且父节点的值不小于大根堆或不大于小根堆它的所有子节点。看起来很简单但真正把它吃透需要回答说三个问题它长什么样、它怎么存、它能干什么。这篇文章适合正在学数据结构的学生、准备考研408的人以及工程里要用到优先队列却一直只会调库不懂原理的开发者。我会从结构约束讲起把操作、建堆、堆排序、工程应用全串一遍最后再说那些面试和考试里最容易翻车的地方。看完之后你对堆的理解应该不只是会用priority_queue这么浅。2. 二叉堆的两条铁律完全二叉树和堆序性堆的第一条定义是完全二叉树。完全二叉树指的是除了最后一层之外每一层都是满的最后一层的节点全部靠左排列。这里要注意完全二叉树和满二叉树不是一回事。满二叉树是每一层都填满完全二叉树允许最后一层不填满但必须从左往右连续填充。举几个例子一棵只有根节点的树是完全二叉树。根节点只有左孩子没有右孩子也是完全二叉树最后一层只填了一个在最左边。根节点只有右孩子没有左孩子不是完全二叉树因为左边空着不连续。第三层节点中间空了哪怕第四层有节点也不像完全二叉树。为什么要卡得这么死这是唯一一个为了存得省服务的设计约束。因为完全二叉树的节点顺序是确定的我们可以直接用数组去存它不需要任何指针。下标从 0 开始算的话映射关系是这样第 i 个节点的左孩子2 \* i 1第 i 个节点的右孩子2 \* i 2第 i 个节点的父节点⌊(i - 1) / 2⌋整数除法向下取整这里最妙的是数组形态的堆天然包含树层级关系却不需要像二叉树链表那样为每个节点存 left、right 指针。一个存 n 个元素的二叉堆数组连续分配就能放下内存局部性极好遍历就是连续下标访问cache 命中率比链表结构的树高一大截。这也是为什么工程上优先队列底层几乎都用堆数组而不是红黑树或链表。第二条铁律是堆序性也叫局部有序大根堆max-heap每个节点的值 ≥ 它的孩子节点。堆顶根节点是全局最大值。小根堆min-heap每个节点的值 ≤ 它的孩子节点。堆顶是全局最小值。去掉最大/最小值恒定在堆顶这条性质后堆内部的其他部分并不是完全有序的。也就是说兄弟节点之间谁大谁小没有任何约定左子树和右子树谁大也没有约定唯一的约束就是父亲永远压着孩子一头大根堆里。这句话是很多初学者容易产生误解的地方——堆不是有序数组堆只是部分有序。它把找最大/最小值这个操作的时间复杂度压缩到了 O(1)但代价是除了最大/最小值之外你想找任意一个元素堆帮不上忙还是得遍历。所以堆的天生定位就是我只需要知道极值不需要知道其他任何顺序信息的场景。3. 上浮与下滤堆操作的两个核心动作所有堆操作都可以归结为两个动作上浮sift up / bubble up和下滤sift down / bubble down。我强烈建议你把这两个词刻在脑子里因为堆的插入、删除、建堆、修改优先级全都是这两个动作的组合。3.1 插入追加到尾部然后上浮往堆里插一个新元素过程分两步先把元素放到数组的最后一位。此时它可能破坏堆序性比祖先大如果是大根堆的话。从这个位置开始不断和父节点比较。如果比父节点大交换继续往上走。直到不比父节点大或者到达根节点。用 C 写大根堆的插入class MaxHeap { vectorint a; public: void push(int x) { a.push_back(x); // 先放到末尾 int i a.size() - 1; while (i 0) { // 上浮 int parent (i - 1) / 2; if (a[i] a[parent]) { swap(a[i], a[parent]); i parent; } else { break; } } } };上浮最坏情况下从叶子节点一路爬到根节点高度是 O(log n)所以插入复杂度 O(log n)。3.2 删除堆顶尾元素顶替再下滤删除最大或最小元素是堆的高频操作也是一般人最容易写错的步骤。为什么不能直接删掉数组第一位因为往回收缩数组的时候如果直接覆盖 0 号元素会留下空洞数组中间空一位完全二叉树性质就毁了。所以标准做法是把根节点和最后一个元素交换或者用最后一个元素覆盖根。pop_back()删掉已经到尾巴上的旧根。新的根大概率不满足堆序性从根开始向下调整比较当前节点和它的左右孩子选出最大大根堆的那个孩子如果孩子更大就交换继续往下走直到不再需要交换。int pop() { int top a[0]; a[0] a.back(); a.pop_back(); int i 0; int n a.size(); while (true) { int l 2 * i 1, r 2 * i 2; int largest i; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest i) break; swap(a[i], a[largest]); i largest; } return top; }3.3 为什么下滤必须考虑两个孩子而上浮只需要比较一个父节点这是我在实际教学中发现的一个高频困惑点值得单独说一下。上浮的时候一个节点只有一个父节点比较关系是唯一的我只要比父节点大就肯定应该往上走因为父节点是唯一管着它的上一级。但是下滤的时候一个节点可能有两个孩子。如果当前节点比左孩子小比右孩子大换还是不换如果要换换左边还是换右边答案是在有右孩子的情况下必须先比较两个孩子选出较大的那个大根堆然后拿当前节点跟这个较大的孩子比较。因为如果你把较小的孩子换上来当父节点虽然比它大的另一个孩子就违反了堆序性等于白调。这个逻辑听起来很简单但在手写heapify的时候极容易漏掉对右孩子存在性的判断。右孩子不一定存在——因为堆是从左到右连续的完全二叉树右孩子存在的前提是左孩子存在而且左右孩子的下标可能越界。我见过很多人在这个边界上栽跟头数组越界或者漏判l n和r n导致奇奇怪怪的 bug。3.4 两个操作的性能幻觉上浮和下滤的复杂度都是 O(log n)都是沿树高走一圈。但在常数项上下滤比上浮要贵一些。因为上浮每一轮固定比较一次、最多交换一次下滤每一轮最多比较三次和左孩子比、和右孩子比、决定之后可能再交换并且每一轮还要做两次分支判断和边界检查。所以在堆操作里优先考虑减少下滤次数能省下不少常数项时间。后面讲 Floyd 建堆法的时候这个性能差异会被进一步放大。4. 自顶向下插入建堆 vs. 自底向上下滤建堆藏着一个 O(n) 的秘密建一个堆最直觉的做法是拿一个空堆把 n 个元素逐个push进去。这就是自顶向下插入建堆法总复杂度是 O(n log n)。这个结果不差很多需要堆的场景已经够用了。但如果你去读《算法导论》或者看面试题会发现还有另一种建堆法复杂度 O(n)。很多人第一次看到这个结论都觉得荒谬n 个元素排一遍序至少 O(n log n)怎么建堆能到 O(n)排序不是比建堆要求更高吗这里最关键的一点建堆不等于排序建堆只需要满足父比子大这种松散的局部约束不需要整体有序。所以它的理论下限不是 O(n log n)线性时间是可能的。4.1 Floyd 建堆法从最后一个非叶节点开始逐个下滤具体做法讲的自底向上的下滤建堆也叫 Floyd 建堆法把 n 个元素随意摆成一个数组。这一步就满足完全二叉树形态大概率不满足堆序性。从最后一个非叶节点开始倒着往前逐个执行下滤。最后一个非叶节点的位置是⌊n/2⌋ - 1下标从 0 算因为排在它后面全都是叶子节点。叶子节点本身就是合法的堆不需要下滤。void buildHeap(vectorint a) { for (int i a.size() / 2 - 1; i 0; --i) { // 这就是个下滤操作复用前面 pop 里的代码 siftDown(a, i, a.size()); } }4.2 为什么是 O(n)账要一层一层算这部分证明是考研、面试最常考的分析题我尽量用不绕的话把它说清楚。先看每个节点下滤的代价节点所在层数越低越靠近叶子它下滤最多能走的路径就越短。具体来说高度为 h 的节点下滤最坏情况下要下沉 h 次。从整棵树的底部往上看高度为 1 的节点数量大约 n/4高度为 2 的节点数量大约 n/8高度为 k 的节点数量大约 n/2^(k1)。总工作量就是T(n) Σ (第 h 层的节点数 × h) Σ (n / 2^(h1)) × h展开这个级数当 n 无限大时Σ h / 2^(h1) 收敛到常数 1。所以总工作量 T(n) O(n)。这就是大部分节点都在底部而底部节点下滤得很快的朴素直觉。和逐个插入的 O(n log n) 对比一下插入法每次都要从最底部开始上浮每个节点平均要走到接近根的高度而 Floyd 建堆法是让大部分节点只走很短的路只有靠近根的少数节点要下滤到较深位置。所以同样是建堆一个 O(n log n)一个 O(n)。4.3 实际工程中用哪个纸上算下来O(n) 比 O(n log n) 快一个数量级。但实际上到底选哪个要看数据来源。如果元素本来就一次性全部拿到比如从一个数组构建堆那绝对用 Floyd 建堆法线性时间白赚。如果元素是流式到达的比如实时信号、事件流没法一次性获得全部数据那就只能逐个 push复杂度就是 O(n log n)。但这种场景下你本来也无法用 Floyd 建堆。这里有一个小坑C 的std::make_heap用的就是 Floyd 建堆时间复杂度严格 O(n)但它要求输入是一个已有的迭代器区间。如果你只想处理增量数据就老老实实用push_heap不要为了线性建堆这个数字强行把数据攒够了再一次性建堆可能内存不够用。5. 堆排序为什么它不是不稳定排序以及 TopK 的真正判断说到堆绕不开堆排序。堆排序可以分成两个阶段第一阶段用 Floyd 建堆把原数组调整成大根堆。第二阶段反复把堆顶最大值和当前最后一个元素交换缩小堆范围后对新的堆顶执行下滤。每轮排好一个当前最大值到数组末尾最终就得到一个升序数组。void heapSort(vectorint a) { buildHeap(a); for (int i a.size() - 1; i 0; --i) { swap(a[0], a[i]); siftDown(a, 0, i); // 注意堆的大小现在是 i } }这个算法时间稳定在 O(n log n)空间复杂度 O(1)不依赖递归、不需要额外数组所以它是手写排序里最省内存的之一。和快速排序相比快排最坏情况 O(n²)堆排序没有这种退化和归并排序相比归并需要 O(n) 辅助空间堆排序原地就能干完。听起来堆排序无懈可击但工程里实际排序库很少用堆排序。原因主要有两个缓存不友好。虽然堆的存储是数组但下滤过程总是跳着访问——从根跳到孙子的孙子跨距越来越大且不规则。归并排序和快排的访问模式则更线性cache 命中率更好。不稳定。这个需要展开讲因为不稳定三个字看似简单实际影响很大。所谓不稳定指相等元素的相对顺序会发生变化。堆排序里经常出现把堆顶换到末尾的操作一旦两个值相等的元素一个在堆顶、一个在子树上交换的一瞬间它们的相对顺序就翻转了。对于按单一 key 排序的场景稳定性无所谓但现实中排序通常带多级条件比如先按分数排再按时间排一旦第一级排序算法不稳定第二级排序的结果就会被破坏。这也是为什么 TimSort 这类稳定排序会成为语言标准库的主流选择。5.1 TopK 问题优先队列的经典应用但要注意规模判断TopK 问题比如从 1000 万个数字里找最大的前 100 个是堆的高频面试题我面试新人的时候几乎必问。标准答案是维护一个小根堆堆的大小固定为 K。每来一个新元素如果它比堆顶当前 K 个候选里最小的那个大就弹出堆顶把它插入否则直接丢弃。最后堆里剩下的就是最大的 K 个。这个方案时间复杂度 O(n log K)。当 n 极大、K 极小时它只需要 O(K) 额外空间这是在内存受限场景下的经典最优解——不管是海量日志、分布式节点上的 top 统计还是数据流这种单遍扫描的方式都不需要把所有数据加载进内存。但这里我想补充一个很多人忽略的判断堆不是 TopK 问题的唯一解选不选堆要看 K 的大小和是否需要在线处理。如果 K 很小比如 K100n1000 万堆方案很合适。如果 K 接近 n/2那就不如直接排序再取前 K 个时间/编码成本都更低。如果数据量小到可以直接放进内存排序后切片可能是最简洁的做法。如果数据特别大但 K 也特别大那么堆的 O(n log K) 依然是最稳的方案。如果数据是流式的、无法回头读取那堆优先队列几乎就是唯一选择。所以面试时不要一听到TopK就条件反射地答堆。先问清楚数据规模、K 的大小、数据是否一次性可读再给出方案。这才是有经验的工程师的思维方式。关于 TopK 还有一个变体找中位数。两堆法用一个小根堆存较大的一半一个大根堆存较小的一半插入时维护两边规模差不超过 1中位数只需要看两边堆顶。这个模型在滑动窗口求中位数、数据流统计里非常常见原理还是堆但多了一层平衡两个堆的思考。这个点尤其值得面试者提前演练因为它能区分出你是背了堆的接口还是真的理解了堆的结构。6. 工程里的堆不止在笔试里出现从定时器到生产调度很多人觉得堆是考试专属工作以后谁还手写堆。实际上堆在底层系统和中间件里到处都是只是大多被封装在库里你天天用却看不见它。6.1 优先队列 堆的标准用途我举三个典型场景任务调度器Timer。服务器上很常见的一种需求是过 3 秒执行任务 A过 10 秒执行任务 B过 10 秒也执行任务 C。如果用普通队列就必须按时钟滴答逐轮扫描所有任务效率低。而用最小堆所有任务按触发时间作为 key 排成堆每次只需 O(1) 看堆顶看下一个该执行的任务是什么到点弹出即可插入新任务 O(log n)。Linux 内核中的高精度定时器、Java 的DelayQueue、各种网络库里的定时器基本都是这个思路。Dijkstra 最短路径。教科书版本用朴素数组找未访问的最小距离复杂度 O(V²)。用了小根堆来取当前离起点最近的点能把复杂度压到 O((V E) log V)这在稀疏图里是质的飞跃。事件驱动系统。网络框架里的 IO 事件、游戏引擎里的碰撞检测、并发编程里的任务队列本质上都需要总是先处理最紧急/优先级最高的事件这种模型这个模型的原型就是优先队列实现就是堆。6.2 系统内存里的堆为什么会出现堆已损坏我记得热搜词里有VS C 堆已损坏还有编译器的堆空间不足这两个和数据结构堆没有直接关系但初学者很容易在考试前被它们干扰。简单说堆已损坏HEAP CORRUPTION DETECTED指运行时分配器管理的内存区域被越界读写破坏了元数据。最常见的原因就是数组越界、缓冲区溢出、或者对一块已释放的内存再次写入。这和二叉堆没有任何关系它只是名字撞了。堆空间不足指的是进程可用的动态内存耗尽跟你写的堆排序没关系。至于堆外内存那是 JVM 里相对 GC 堆之外的内存区域的叫法同样只是词面巧合。我建议你也别把这几个概念搅在一起记。遇到调试器报堆已损坏正确的排查思路是是不是哪块内存越界了而不是我的二叉堆写错了什么。方向错了排查速度会差很多。6.3 语言标准库中的堆实现主流语言基本都内建了优先队列语言/库容器特点Cqueuestd::priority_queue默认大根堆可通过greater改小根堆需要手写三个自由函数时可用make_heap/push_heap/pop_heapPythonheapqheapq默认小根堆模块级函数操作 listheappush/heappop/heapifyJavaPriorityQueue默认小根堆Gocontainer/heap需要实现heap.Interface接口灵活性更强这里有一个很实际的提醒标准库里的优先队列大多不支持修改堆中任意元素的优先级这个操作。如果业务需要找到堆里的某个元素并更新它的 key直接用标准库会很别扭。一个典型的例子是 Dijkstra 优化中需要松弛操作更新一个已经入堆的点的距离。相比之下正确做法是允许堆里有重复旧数据每次更新时 push 一个新值取出来的时候判断这个值是否过期如果是旧值就丢弃。这是懒惰删除策略也是实际工程里最常见的做法。但如果你想严肃地做 decrease-key让堆中每个元素都追踪其索引就需要自己实现一个索引堆Index Heap并维护pos数组。索引堆在带修改的图算法里很有用笔试中也偶尔考到值得另外花时间研究。7. 大根堆和小根堆的几个易错点下标、边界和变体7.1 下标起点和父子关系别记混很多教材和 Online Judge 模板用 1 作为数组起点根在下标 1这时父子关系变为左孩子2*i右孩子2*i1父节点i/2用 0 作为起点时是2*i1、2*i2、(i-1)/2。两种写法都能用但如果你把两套公式混着用BUG 会非常隐蔽。我见过最典型的问题模板里用 0 起点手写快排时习惯性写i / 2找父节点结果在某些情况下算出来的父节点是错的堆序时好时坏。建议固定一种并在代码上写上注释。7.2 下滤的时候堆的大小是变化的堆排序第二阶段特别容易错siftDown的边界必须是当前待排序区间的大小而不是数组原始大小。写排序的时候每次 swap 完倒数第二个元素堆的有效长度就减一。不少人误用了原始数组长度结果刚换到末尾的已排序元素又被拉回堆里参与下滤排序结果一塌糊涂。这个 bug 在数据量小时不一定会暴露但在 n 较大时几乎必然出错。我在给合作方做代码 review 的时候见过不止一次是最典型的养在平静期、爆在测试期的错误。7.3 二叉堆和二叉搜索树的本质区别这个问题很适合用来检验理解。二叉搜索树BST约束是左子树所有节点 根 右子树所有节点它维护的是一个完整的偏序结构适合范围查询、求前驱后继、中序遍历输出有序序列。堆只约束父子和孩子的相对大小无法像 BST 那样做折半查找、范围查询它只擅长找极值。堆的中序遍历不是有序的这句话在面试里也是个经典问题。重点是因为堆完全是按数组/逐层编号来组织的它的中序遍历顺序是由节点所在的空间位置决定的跟值的大小关系毫无关系。有序性只体现在从堆顶往下沿一条路径的过程中而不是任何线性遍历顺序。7.4 线索二叉树跟堆没关系但总有人放在一起搜热搜词里出现了线索二叉树这通常是另一个学习阶段的困惑。线索二叉树是为解决普通二叉树遍历时如何找前驱/后继而引入的优化它利用空闲指针记录遍历序列的前驱后继关系跟堆完全是两回事。不要因为课程讲了二叉树就把所有树混在一起。二叉树是一个大类堆是其中一种结构上受限、内容上有序的特例而 BST、AVL、红黑树、线索树是各自的变体逻辑边界要清晰。8. 一个综合案例用堆设计一个带过期时间的任务调度器纸上谈兵到此为止我提供一个可以直接上手的综合练手项目。目标是实现一个简单的定时任务调度器 TaskScheduler功能如下支持delay(ms, callback)注册一个 ms 毫秒后执行的任务。支持run()在单线程循环中执行到期的任务。支持任务取消按任务 ID。核心设计使用小根堆存任务key 是触发时间戳。每次run时不断看堆顶如果堆顶的触发时间已经不大于当前时间就弹出并执行否则就sleep到堆顶时间或忙等。我在一次内部工具开发中就是按这个结构写的。它本质上是一个用heapq或者std::priority_queue就能实现的事件队列但因为任务会取消所以需要懒惰删除每次弹出一个任务时先判断它的版本号/是否已取消再决定执行还是丢弃。这个练手项目你可以用任意语言实现建议做一个简单的 http 接口接收任务请求把任务塞进堆里用一个 goroutine / 线程跑run循环。做完这个项目之后你会发现堆不再是抽象的算法而是你真的能掌控的工具。9. 给备考者和面试者的最后几点建议最后聊一点实用的备考和面试经验纯个人体会供你们参考。第一一定要能手写堆的核心操作。我看过太多人在面试里写PriorityQueue调包调得飞起一旦让对方手写 TopK连siftDown的边界条件都写不对。建议背模板但不背死模板——理解为什么最后一个非叶节点是n/2 - 1「为什么弹出的元素要放末尾再下滤」这些如果只是背遇到变体题就容易崩。第二多练手撕两堆找中位数这种组合题。它比单纯堆排序更能检验你理解堆的深度也是面试官常用的进阶题。核心难点在插入时如何平衡两个堆的规模差不超过 1以及堆顶如何维护正确的中位数。第三性能估算要落在常数上。小根堆和大根堆的复杂度都是 O(log n)但一个从叶子向上浮一个从根向下滤常数项完全不同。能够说出来弗洛伊德建堆是 O(n) 但常数也小而插入建堆是 O(n log n)这种细节会让面试官觉得你真的是在做工程而不是背教科书。第四学会区分要稳定和只要极值这两种场景。遇到取当前最紧急的任务取数据流最大的 K 个找最短路径的下一个扩展点这类需求优先想到堆。遇到我要输出排序结果我要范围查询这类需求不要去用堆红黑树或平衡查找树才是对的工具。工程上的很多架构决策归根结底就是在我关心谁最大和我关心谁在哪儿之间做选择而堆恰好只解决前者。好了堆的内容到这里基本闭环了。如果你也是那种上课听懂了、一到手写就卡壳的人我的建议特别简单你不是笨是缺一次真实的坏堆调试经历。自己亲手写一个优先队列写完之后扔进去 100 万个随机数用std::sort的结果逐项对着验出错就打印每一层堆的结构调通一次之后你对堆的认知就再也不会停留在好像懂了的层面了。 二叉堆详解：原理、建堆、堆排序与工程应用实战
1. 为什么堆和堆总让人分不清先说名字里的坑我第一次学数据结构时最崩溃的地方不是算法本身而是堆这个名字。操作系统课里说堆是动态分配内存的区域JVM调优时说堆外内存C报错说堆已损坏结果数据结构课又冒出来一个堆还是个二叉树。三个堆字说的完全不是一回事。当年我在论坛上看到有人问堆和栈的区别下面的人吵了三百楼——因为有人答内存布局有人答数据结构还有人答的是调用栈。谁都对谁都没对上频道。所以这篇文章开篇第一件事就是把概念边界先画清楚。操作系统/运行时里的堆heap一段用来动态分配内存的区域由malloc、new、GC 等机制管理和数据结构没有直接关系。系统栈stack函数调用时压栈的帧结构先进后出和栈这种数据结构确实同构但它是运行时机制。数据结构里的堆heap一种完全二叉树形态的树形结构满足特定的大小关系约束。本文要讲的就是这个东西。这三个概念共享堆这个词纯属历史遗留习惯没有任何深奥原因。你要是非要找一点共性勉强可以说操作系统里的堆在分配内存时倾向于把碎片化的小块拼成大块和数据结构的堆动态调整优先级的思想有一点点神似但这个类比站不住脚最大的作用就是考试之前别把自己绕晕。数据结构里的堆大多数教材会给出一个定义一棵完全二叉树并且父节点的值不小于大根堆或不大于小根堆它的所有子节点。看起来很简单但真正把它吃透需要回答说三个问题它长什么样、它怎么存、它能干什么。这篇文章适合正在学数据结构的学生、准备考研408的人以及工程里要用到优先队列却一直只会调库不懂原理的开发者。我会从结构约束讲起把操作、建堆、堆排序、工程应用全串一遍最后再说那些面试和考试里最容易翻车的地方。看完之后你对堆的理解应该不只是会用priority_queue这么浅。2. 二叉堆的两条铁律完全二叉树和堆序性堆的第一条定义是完全二叉树。完全二叉树指的是除了最后一层之外每一层都是满的最后一层的节点全部靠左排列。这里要注意完全二叉树和满二叉树不是一回事。满二叉树是每一层都填满完全二叉树允许最后一层不填满但必须从左往右连续填充。举几个例子一棵只有根节点的树是完全二叉树。根节点只有左孩子没有右孩子也是完全二叉树最后一层只填了一个在最左边。根节点只有右孩子没有左孩子不是完全二叉树因为左边空着不连续。第三层节点中间空了哪怕第四层有节点也不像完全二叉树。为什么要卡得这么死这是唯一一个为了存得省服务的设计约束。因为完全二叉树的节点顺序是确定的我们可以直接用数组去存它不需要任何指针。下标从 0 开始算的话映射关系是这样第 i 个节点的左孩子2 \* i 1第 i 个节点的右孩子2 \* i 2第 i 个节点的父节点⌊(i - 1) / 2⌋整数除法向下取整这里最妙的是数组形态的堆天然包含树层级关系却不需要像二叉树链表那样为每个节点存 left、right 指针。一个存 n 个元素的二叉堆数组连续分配就能放下内存局部性极好遍历就是连续下标访问cache 命中率比链表结构的树高一大截。这也是为什么工程上优先队列底层几乎都用堆数组而不是红黑树或链表。第二条铁律是堆序性也叫局部有序大根堆max-heap每个节点的值 ≥ 它的孩子节点。堆顶根节点是全局最大值。小根堆min-heap每个节点的值 ≤ 它的孩子节点。堆顶是全局最小值。去掉最大/最小值恒定在堆顶这条性质后堆内部的其他部分并不是完全有序的。也就是说兄弟节点之间谁大谁小没有任何约定左子树和右子树谁大也没有约定唯一的约束就是父亲永远压着孩子一头大根堆里。这句话是很多初学者容易产生误解的地方——堆不是有序数组堆只是部分有序。它把找最大/最小值这个操作的时间复杂度压缩到了 O(1)但代价是除了最大/最小值之外你想找任意一个元素堆帮不上忙还是得遍历。所以堆的天生定位就是我只需要知道极值不需要知道其他任何顺序信息的场景。3. 上浮与下滤堆操作的两个核心动作所有堆操作都可以归结为两个动作上浮sift up / bubble up和下滤sift down / bubble down。我强烈建议你把这两个词刻在脑子里因为堆的插入、删除、建堆、修改优先级全都是这两个动作的组合。3.1 插入追加到尾部然后上浮往堆里插一个新元素过程分两步先把元素放到数组的最后一位。此时它可能破坏堆序性比祖先大如果是大根堆的话。从这个位置开始不断和父节点比较。如果比父节点大交换继续往上走。直到不比父节点大或者到达根节点。用 C 写大根堆的插入class MaxHeap { vectorint a; public: void push(int x) { a.push_back(x); // 先放到末尾 int i a.size() - 1; while (i 0) { // 上浮 int parent (i - 1) / 2; if (a[i] a[parent]) { swap(a[i], a[parent]); i parent; } else { break; } } } };上浮最坏情况下从叶子节点一路爬到根节点高度是 O(log n)所以插入复杂度 O(log n)。3.2 删除堆顶尾元素顶替再下滤删除最大或最小元素是堆的高频操作也是一般人最容易写错的步骤。为什么不能直接删掉数组第一位因为往回收缩数组的时候如果直接覆盖 0 号元素会留下空洞数组中间空一位完全二叉树性质就毁了。所以标准做法是把根节点和最后一个元素交换或者用最后一个元素覆盖根。pop_back()删掉已经到尾巴上的旧根。新的根大概率不满足堆序性从根开始向下调整比较当前节点和它的左右孩子选出最大大根堆的那个孩子如果孩子更大就交换继续往下走直到不再需要交换。int pop() { int top a[0]; a[0] a.back(); a.pop_back(); int i 0; int n a.size(); while (true) { int l 2 * i 1, r 2 * i 2; int largest i; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest i) break; swap(a[i], a[largest]); i largest; } return top; }3.3 为什么下滤必须考虑两个孩子而上浮只需要比较一个父节点这是我在实际教学中发现的一个高频困惑点值得单独说一下。上浮的时候一个节点只有一个父节点比较关系是唯一的我只要比父节点大就肯定应该往上走因为父节点是唯一管着它的上一级。但是下滤的时候一个节点可能有两个孩子。如果当前节点比左孩子小比右孩子大换还是不换如果要换换左边还是换右边答案是在有右孩子的情况下必须先比较两个孩子选出较大的那个大根堆然后拿当前节点跟这个较大的孩子比较。因为如果你把较小的孩子换上来当父节点虽然比它大的另一个孩子就违反了堆序性等于白调。这个逻辑听起来很简单但在手写heapify的时候极容易漏掉对右孩子存在性的判断。右孩子不一定存在——因为堆是从左到右连续的完全二叉树右孩子存在的前提是左孩子存在而且左右孩子的下标可能越界。我见过很多人在这个边界上栽跟头数组越界或者漏判l n和r n导致奇奇怪怪的 bug。3.4 两个操作的性能幻觉上浮和下滤的复杂度都是 O(log n)都是沿树高走一圈。但在常数项上下滤比上浮要贵一些。因为上浮每一轮固定比较一次、最多交换一次下滤每一轮最多比较三次和左孩子比、和右孩子比、决定之后可能再交换并且每一轮还要做两次分支判断和边界检查。所以在堆操作里优先考虑减少下滤次数能省下不少常数项时间。后面讲 Floyd 建堆法的时候这个性能差异会被进一步放大。4. 自顶向下插入建堆 vs. 自底向上下滤建堆藏着一个 O(n) 的秘密建一个堆最直觉的做法是拿一个空堆把 n 个元素逐个push进去。这就是自顶向下插入建堆法总复杂度是 O(n log n)。这个结果不差很多需要堆的场景已经够用了。但如果你去读《算法导论》或者看面试题会发现还有另一种建堆法复杂度 O(n)。很多人第一次看到这个结论都觉得荒谬n 个元素排一遍序至少 O(n log n)怎么建堆能到 O(n)排序不是比建堆要求更高吗这里最关键的一点建堆不等于排序建堆只需要满足父比子大这种松散的局部约束不需要整体有序。所以它的理论下限不是 O(n log n)线性时间是可能的。4.1 Floyd 建堆法从最后一个非叶节点开始逐个下滤具体做法讲的自底向上的下滤建堆也叫 Floyd 建堆法把 n 个元素随意摆成一个数组。这一步就满足完全二叉树形态大概率不满足堆序性。从最后一个非叶节点开始倒着往前逐个执行下滤。最后一个非叶节点的位置是⌊n/2⌋ - 1下标从 0 算因为排在它后面全都是叶子节点。叶子节点本身就是合法的堆不需要下滤。void buildHeap(vectorint a) { for (int i a.size() / 2 - 1; i 0; --i) { // 这就是个下滤操作复用前面 pop 里的代码 siftDown(a, i, a.size()); } }4.2 为什么是 O(n)账要一层一层算这部分证明是考研、面试最常考的分析题我尽量用不绕的话把它说清楚。先看每个节点下滤的代价节点所在层数越低越靠近叶子它下滤最多能走的路径就越短。具体来说高度为 h 的节点下滤最坏情况下要下沉 h 次。从整棵树的底部往上看高度为 1 的节点数量大约 n/4高度为 2 的节点数量大约 n/8高度为 k 的节点数量大约 n/2^(k1)。总工作量就是T(n) Σ (第 h 层的节点数 × h) Σ (n / 2^(h1)) × h展开这个级数当 n 无限大时Σ h / 2^(h1) 收敛到常数 1。所以总工作量 T(n) O(n)。这就是大部分节点都在底部而底部节点下滤得很快的朴素直觉。和逐个插入的 O(n log n) 对比一下插入法每次都要从最底部开始上浮每个节点平均要走到接近根的高度而 Floyd 建堆法是让大部分节点只走很短的路只有靠近根的少数节点要下滤到较深位置。所以同样是建堆一个 O(n log n)一个 O(n)。4.3 实际工程中用哪个纸上算下来O(n) 比 O(n log n) 快一个数量级。但实际上到底选哪个要看数据来源。如果元素本来就一次性全部拿到比如从一个数组构建堆那绝对用 Floyd 建堆法线性时间白赚。如果元素是流式到达的比如实时信号、事件流没法一次性获得全部数据那就只能逐个 push复杂度就是 O(n log n)。但这种场景下你本来也无法用 Floyd 建堆。这里有一个小坑C 的std::make_heap用的就是 Floyd 建堆时间复杂度严格 O(n)但它要求输入是一个已有的迭代器区间。如果你只想处理增量数据就老老实实用push_heap不要为了线性建堆这个数字强行把数据攒够了再一次性建堆可能内存不够用。5. 堆排序为什么它不是不稳定排序以及 TopK 的真正判断说到堆绕不开堆排序。堆排序可以分成两个阶段第一阶段用 Floyd 建堆把原数组调整成大根堆。第二阶段反复把堆顶最大值和当前最后一个元素交换缩小堆范围后对新的堆顶执行下滤。每轮排好一个当前最大值到数组末尾最终就得到一个升序数组。void heapSort(vectorint a) { buildHeap(a); for (int i a.size() - 1; i 0; --i) { swap(a[0], a[i]); siftDown(a, 0, i); // 注意堆的大小现在是 i } }这个算法时间稳定在 O(n log n)空间复杂度 O(1)不依赖递归、不需要额外数组所以它是手写排序里最省内存的之一。和快速排序相比快排最坏情况 O(n²)堆排序没有这种退化和归并排序相比归并需要 O(n) 辅助空间堆排序原地就能干完。听起来堆排序无懈可击但工程里实际排序库很少用堆排序。原因主要有两个缓存不友好。虽然堆的存储是数组但下滤过程总是跳着访问——从根跳到孙子的孙子跨距越来越大且不规则。归并排序和快排的访问模式则更线性cache 命中率更好。不稳定。这个需要展开讲因为不稳定三个字看似简单实际影响很大。所谓不稳定指相等元素的相对顺序会发生变化。堆排序里经常出现把堆顶换到末尾的操作一旦两个值相等的元素一个在堆顶、一个在子树上交换的一瞬间它们的相对顺序就翻转了。对于按单一 key 排序的场景稳定性无所谓但现实中排序通常带多级条件比如先按分数排再按时间排一旦第一级排序算法不稳定第二级排序的结果就会被破坏。这也是为什么 TimSort 这类稳定排序会成为语言标准库的主流选择。5.1 TopK 问题优先队列的经典应用但要注意规模判断TopK 问题比如从 1000 万个数字里找最大的前 100 个是堆的高频面试题我面试新人的时候几乎必问。标准答案是维护一个小根堆堆的大小固定为 K。每来一个新元素如果它比堆顶当前 K 个候选里最小的那个大就弹出堆顶把它插入否则直接丢弃。最后堆里剩下的就是最大的 K 个。这个方案时间复杂度 O(n log K)。当 n 极大、K 极小时它只需要 O(K) 额外空间这是在内存受限场景下的经典最优解——不管是海量日志、分布式节点上的 top 统计还是数据流这种单遍扫描的方式都不需要把所有数据加载进内存。但这里我想补充一个很多人忽略的判断堆不是 TopK 问题的唯一解选不选堆要看 K 的大小和是否需要在线处理。如果 K 很小比如 K100n1000 万堆方案很合适。如果 K 接近 n/2那就不如直接排序再取前 K 个时间/编码成本都更低。如果数据量小到可以直接放进内存排序后切片可能是最简洁的做法。如果数据特别大但 K 也特别大那么堆的 O(n log K) 依然是最稳的方案。如果数据是流式的、无法回头读取那堆优先队列几乎就是唯一选择。所以面试时不要一听到TopK就条件反射地答堆。先问清楚数据规模、K 的大小、数据是否一次性可读再给出方案。这才是有经验的工程师的思维方式。关于 TopK 还有一个变体找中位数。两堆法用一个小根堆存较大的一半一个大根堆存较小的一半插入时维护两边规模差不超过 1中位数只需要看两边堆顶。这个模型在滑动窗口求中位数、数据流统计里非常常见原理还是堆但多了一层平衡两个堆的思考。这个点尤其值得面试者提前演练因为它能区分出你是背了堆的接口还是真的理解了堆的结构。6. 工程里的堆不止在笔试里出现从定时器到生产调度很多人觉得堆是考试专属工作以后谁还手写堆。实际上堆在底层系统和中间件里到处都是只是大多被封装在库里你天天用却看不见它。6.1 优先队列 堆的标准用途我举三个典型场景任务调度器Timer。服务器上很常见的一种需求是过 3 秒执行任务 A过 10 秒执行任务 B过 10 秒也执行任务 C。如果用普通队列就必须按时钟滴答逐轮扫描所有任务效率低。而用最小堆所有任务按触发时间作为 key 排成堆每次只需 O(1) 看堆顶看下一个该执行的任务是什么到点弹出即可插入新任务 O(log n)。Linux 内核中的高精度定时器、Java 的DelayQueue、各种网络库里的定时器基本都是这个思路。Dijkstra 最短路径。教科书版本用朴素数组找未访问的最小距离复杂度 O(V²)。用了小根堆来取当前离起点最近的点能把复杂度压到 O((V E) log V)这在稀疏图里是质的飞跃。事件驱动系统。网络框架里的 IO 事件、游戏引擎里的碰撞检测、并发编程里的任务队列本质上都需要总是先处理最紧急/优先级最高的事件这种模型这个模型的原型就是优先队列实现就是堆。6.2 系统内存里的堆为什么会出现堆已损坏我记得热搜词里有VS C 堆已损坏还有编译器的堆空间不足这两个和数据结构堆没有直接关系但初学者很容易在考试前被它们干扰。简单说堆已损坏HEAP CORRUPTION DETECTED指运行时分配器管理的内存区域被越界读写破坏了元数据。最常见的原因就是数组越界、缓冲区溢出、或者对一块已释放的内存再次写入。这和二叉堆没有任何关系它只是名字撞了。堆空间不足指的是进程可用的动态内存耗尽跟你写的堆排序没关系。至于堆外内存那是 JVM 里相对 GC 堆之外的内存区域的叫法同样只是词面巧合。我建议你也别把这几个概念搅在一起记。遇到调试器报堆已损坏正确的排查思路是是不是哪块内存越界了而不是我的二叉堆写错了什么。方向错了排查速度会差很多。6.3 语言标准库中的堆实现主流语言基本都内建了优先队列语言/库容器特点Cqueuestd::priority_queue默认大根堆可通过greater改小根堆需要手写三个自由函数时可用make_heap/push_heap/pop_heapPythonheapqheapq默认小根堆模块级函数操作 listheappush/heappop/heapifyJavaPriorityQueue默认小根堆Gocontainer/heap需要实现heap.Interface接口灵活性更强这里有一个很实际的提醒标准库里的优先队列大多不支持修改堆中任意元素的优先级这个操作。如果业务需要找到堆里的某个元素并更新它的 key直接用标准库会很别扭。一个典型的例子是 Dijkstra 优化中需要松弛操作更新一个已经入堆的点的距离。相比之下正确做法是允许堆里有重复旧数据每次更新时 push 一个新值取出来的时候判断这个值是否过期如果是旧值就丢弃。这是懒惰删除策略也是实际工程里最常见的做法。但如果你想严肃地做 decrease-key让堆中每个元素都追踪其索引就需要自己实现一个索引堆Index Heap并维护pos数组。索引堆在带修改的图算法里很有用笔试中也偶尔考到值得另外花时间研究。7. 大根堆和小根堆的几个易错点下标、边界和变体7.1 下标起点和父子关系别记混很多教材和 Online Judge 模板用 1 作为数组起点根在下标 1这时父子关系变为左孩子2*i右孩子2*i1父节点i/2用 0 作为起点时是2*i1、2*i2、(i-1)/2。两种写法都能用但如果你把两套公式混着用BUG 会非常隐蔽。我见过最典型的问题模板里用 0 起点手写快排时习惯性写i / 2找父节点结果在某些情况下算出来的父节点是错的堆序时好时坏。建议固定一种并在代码上写上注释。7.2 下滤的时候堆的大小是变化的堆排序第二阶段特别容易错siftDown的边界必须是当前待排序区间的大小而不是数组原始大小。写排序的时候每次 swap 完倒数第二个元素堆的有效长度就减一。不少人误用了原始数组长度结果刚换到末尾的已排序元素又被拉回堆里参与下滤排序结果一塌糊涂。这个 bug 在数据量小时不一定会暴露但在 n 较大时几乎必然出错。我在给合作方做代码 review 的时候见过不止一次是最典型的养在平静期、爆在测试期的错误。7.3 二叉堆和二叉搜索树的本质区别这个问题很适合用来检验理解。二叉搜索树BST约束是左子树所有节点 根 右子树所有节点它维护的是一个完整的偏序结构适合范围查询、求前驱后继、中序遍历输出有序序列。堆只约束父子和孩子的相对大小无法像 BST 那样做折半查找、范围查询它只擅长找极值。堆的中序遍历不是有序的这句话在面试里也是个经典问题。重点是因为堆完全是按数组/逐层编号来组织的它的中序遍历顺序是由节点所在的空间位置决定的跟值的大小关系毫无关系。有序性只体现在从堆顶往下沿一条路径的过程中而不是任何线性遍历顺序。7.4 线索二叉树跟堆没关系但总有人放在一起搜热搜词里出现了线索二叉树这通常是另一个学习阶段的困惑。线索二叉树是为解决普通二叉树遍历时如何找前驱/后继而引入的优化它利用空闲指针记录遍历序列的前驱后继关系跟堆完全是两回事。不要因为课程讲了二叉树就把所有树混在一起。二叉树是一个大类堆是其中一种结构上受限、内容上有序的特例而 BST、AVL、红黑树、线索树是各自的变体逻辑边界要清晰。8. 一个综合案例用堆设计一个带过期时间的任务调度器纸上谈兵到此为止我提供一个可以直接上手的综合练手项目。目标是实现一个简单的定时任务调度器 TaskScheduler功能如下支持delay(ms, callback)注册一个 ms 毫秒后执行的任务。支持run()在单线程循环中执行到期的任务。支持任务取消按任务 ID。核心设计使用小根堆存任务key 是触发时间戳。每次run时不断看堆顶如果堆顶的触发时间已经不大于当前时间就弹出并执行否则就sleep到堆顶时间或忙等。我在一次内部工具开发中就是按这个结构写的。它本质上是一个用heapq或者std::priority_queue就能实现的事件队列但因为任务会取消所以需要懒惰删除每次弹出一个任务时先判断它的版本号/是否已取消再决定执行还是丢弃。这个练手项目你可以用任意语言实现建议做一个简单的 http 接口接收任务请求把任务塞进堆里用一个 goroutine / 线程跑run循环。做完这个项目之后你会发现堆不再是抽象的算法而是你真的能掌控的工具。9. 给备考者和面试者的最后几点建议最后聊一点实用的备考和面试经验纯个人体会供你们参考。第一一定要能手写堆的核心操作。我看过太多人在面试里写PriorityQueue调包调得飞起一旦让对方手写 TopK连siftDown的边界条件都写不对。建议背模板但不背死模板——理解为什么最后一个非叶节点是n/2 - 1「为什么弹出的元素要放末尾再下滤」这些如果只是背遇到变体题就容易崩。第二多练手撕两堆找中位数这种组合题。它比单纯堆排序更能检验你理解堆的深度也是面试官常用的进阶题。核心难点在插入时如何平衡两个堆的规模差不超过 1以及堆顶如何维护正确的中位数。第三性能估算要落在常数上。小根堆和大根堆的复杂度都是 O(log n)但一个从叶子向上浮一个从根向下滤常数项完全不同。能够说出来弗洛伊德建堆是 O(n) 但常数也小而插入建堆是 O(n log n)这种细节会让面试官觉得你真的是在做工程而不是背教科书。第四学会区分要稳定和只要极值这两种场景。遇到取当前最紧急的任务取数据流最大的 K 个找最短路径的下一个扩展点这类需求优先想到堆。遇到我要输出排序结果我要范围查询这类需求不要去用堆红黑树或平衡查找树才是对的工具。工程上的很多架构决策归根结底就是在我关心谁最大和我关心谁在哪儿之间做选择而堆恰好只解决前者。好了堆的内容到这里基本闭环了。如果你也是那种上课听懂了、一到手写就卡壳的人我的建议特别简单你不是笨是缺一次真实的坏堆调试经历。自己亲手写一个优先队列写完之后扔进去 100 万个随机数用std::sort的结果逐项对着验出错就打印每一层堆的结构调通一次之后你对堆的认知就再也不会停留在好像懂了的层面了。