1. 说在前面hot100里的“堆”到底是什么这两年铺天盖地的LeetCode Hot 100刷题清单很多人一上来就按顺序从两数之和开刷刷到树和图就开始崩溃然后跳过一堆题目。说实话Hot 100里跟堆Heap相关的题其实不算多标签里明确带“堆”的也就七八道左右但它恰恰是面试中被问得最频繁的数据结构之一尤其是大厂一面、二面的手撕代码环节TopK、中位数、多路归并这几个经典场景十次有八次会出现在白板上。先说清一个概念这里讨论的“堆”是数据结构中的二叉堆Binary Heap不是操作系统或者JVM里那个“内存堆”。虽然热词里有人搜“编译器的堆空间不足”“堆外内存”那是另一个维度的概念指的是动态内存分配区域。两者同名但完全不同刷题的时候千万别混。Hot 100里的堆题核心就一句话利用大小根堆的堆顶特性以O(log n)的代价维护一个有序的窗口或集合。你不需要会手写复杂平衡树也不需要会Treap、Splay能把优先队列Priority Queue用顺再明白它背后是怎么用数组模拟完全二叉树的就足够应付绝大多数题目。这篇文章把我的刷题笔记、面试现场踩过的坑、以及对每道hot100堆题的理解全部整理出来包含可直接抄的模板代码、复杂度分析、以及面试追问时的应对思路。不管你是刚开始刷题的新手还是准备冲刺大厂的老兵这套内容应该都能帮上忙。2. 堆的底层原理与hot100堆题的题型分布2.1 堆的本质用数组模拟的完全二叉树堆在逻辑上是一棵完全二叉树但在物理存储上就是一个数组。对于一个下标从0开始的数组节点i的左孩子是2i1右孩子是2i2父节点是(i-1)/2。之所以能用数组存正是因为完全二叉树每一层都是从左到右紧密排列的中间不会出现空洞。大根堆的性质是每个节点的值都大于等于它的左右孩子所以堆顶就是这个堆里的最大值小根堆正好相反堆顶是最小值。注意堆只保证父子之间的有序性不保证兄弟节点之间的顺序这是堆和二叉搜索树的本质区别。很多人刚开始会把堆和排序树搞混记住一点二叉搜索树可以中序遍历得到有序序列堆做不到堆只能保证堆顶是极值。这个“只保证堆顶有序”的特性决定了堆适合解决“我只关心最大/最小的那一个或那一批”的问题。如果你需要全局有序应该用排序如果只需要动态维护极值、局部有序堆就是成本最低的选择。2.2 手写堆的两个核心操作上浮与下沉虽然日常刷题可以直接用语言内置的优先队列但面试官有时候会追问“优先队列是怎么实现的”甚至会要求手写一个堆。这时候如果你只知道调API场面会很尴尬。手写堆就两个核心操作上浮swim / shift-up新元素插入到数组末尾然后不断和父节点比较如果不满足堆性质就交换直到满足为止。用于插入操作。下沉sink / shift-down把某个节点和它的左右孩子中较大的那个大根堆比较如果父节点小就交换然后继续下沉。用于删除堆顶或者堆排序。插入一个元素先放到末尾然后上浮删除堆顶把末尾元素放到堆顶然后下沉。两个操作的时间复杂度都是O(log n)因为完全二叉树的高度是log n。下面给一份大根堆手写模板我建议每个准备面试的人都默写一遍class MaxHeap { private: vectorint a; void swim(int i) { while (i 0 a[(i - 1) / 2] a[i]) { swap(a[(i - 1) / 2], a[i]); i (i - 1) / 2; } } void sink(int i) { int n a.size(); while (2 * i 1 n) { int j 2 * i 1; if (j 1 n a[j 1] a[j]) j; if (a[i] a[j]) break; swap(a[i], a[j]); i j; } } public: void push(int x) { a.push_back(x); swim(a.size() - 1); } int top() { return a[0]; } void pop() { a[0] a.back(); a.pop_back(); sink(0); } };这份代码面试时非常加分。它能让你在白板上跟面试官聊清楚“为什么优先队列的时间复杂度是O(log n)”“堆排序为什么不稳定”这类追问。堆排序不稳定是因为堆调整过程中会跳过间隔元素相同值的相对顺序无法保证。2.3 hot100堆题的三大模式把hot100里的堆题全部过一遍你会发现它们本质上是三类问题第一类TopK问题。核心套路维护一个大小为k的堆求第K大用最小堆求第K小用最大堆。这类的代表是215. 数组中的第K个最大元素、347. 前K个高频元素。为什么求第K大要用小根堆因为小根堆的堆顶是堆里最小的元素当堆的大小超过k时堆顶就是“目前这k1个元素里最不该保留的”把它弹掉剩下k个就是目前最大的k个。遍历完整个数组后堆顶就是第K大的那个。第二类多路归并问题。多个有序序列要合并成一个有序序列每次从所有序列的当前指针中取最小的那个。用一个大小为路数的小根堆堆顶就是当前最小的元素。代表是23. 合并K个升序链表。这类题的关键是堆里存的不只是值还需要记录这个值来自哪一路、以及当前走到哪了。第三类动态数据流问题。数据不断插入随时需要查极值或中位数。代表是295. 数据流的中位数用一个最大堆和一个最小堆相互配合。这类题的关键是堆的“动态调整”每插入一个数就要维护两个堆的平衡。明白了这三类模式hot100里所有堆题都有了解题框架。下面我按题目逐个拆解。3. hot100堆题逐个拆解思路、代码与易错点3.1 215. 数组中的第K个最大元素这是堆题里最经典的一道也是TopK问题的原型。题目给你一个无序数组要求返回数组中第K个最大的元素注意不是第K个不同元素。用堆的解法非常直观int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; // 小根堆 for (int x : nums) { pq.push(x); if (pq.size() k) pq.pop(); } return pq.top(); }时间复杂度O(n log k)空间复杂度O(k)。当k远小于n时这个复杂度优于直接排序的O(n log n)。面试官几乎一定会追问的替代方案是快速选择Quick Select基于快排的partition思想平均O(n)最坏O(n^2)。我个人的建议是面试时优先答堆因为代码短、思路清晰如果面试官追问“能不能更快”再提快速选择并且要能说明它的平均复杂度和随机化改进。注意一个细节C的priority_queueint, vectorint, greaterint是小根堆如果你用的是Java的PriorityQueueInteger默认就是小根堆Python的heapq默认也是小根堆。真正容易坑的是C因为priority_queue默认是大根堆想用小根堆必须带全三个模板参数。很多初学者在这里写错结果求第K大变成求第K小。3.2 347. 前K个高频元素这道题是哈希表 堆的经典组合。先统计每个数字的出现次数然后用一个大小为k的小根堆维护“当前出现频率最高的k个元素”堆顶是这k个里频率最低的。新元素频率比堆顶高时替换堆顶。vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int freq; for (int x : nums) freq[x]; // 小根堆pair频率, 元素值 auto cmp [](pairint, int a, pairint, int b) { return a.first b.first; }; priority_queuepairint, int, vectorpairint, int, decltype(cmp) pq(cmp); for (auto [val, f] : freq) { pq.push({f, val}); if (pq.size() k) pq.pop(); } vectorint res; while (!pq.empty()) { res.push_back(pq.top().second); pq.pop(); } return res; }这里有个容易踩的坑C用lambda做比较器时返回true表示第一个参数的优先级低于第二个参数。很多人从sort的习惯过来sort的lambda返回true表示第一个参数排在前面但priority_queue的规则是反直觉的。比如return a.first b.first意思是频率大的在堆底、频率小的在堆顶形成小根堆。如果你照搬sort的写法return a.first b.first你会得到一个最大堆堆顶是频率最高的弹出它的时候恰恰会把正确答案丢掉。这也是我建议面试时多用语言内置API的原因之一但你必须清楚API底层的行为。想验证自己有没有理解错就在本地跑一段几行的小代码打印堆顶输出看一眼。这道题的时间复杂度是O(n log k)因为哈希遍历是O(n)堆操作是O(log k)。如果要追求极致还可以用桶排序思想做到O(n)把频率作为数组下标从高到低收集元素。面试中能说出这个优化会很加分。3.3 295. 数据流的中位数这道题的难度在hot100里属于中上核心技巧是“双堆”一个最大堆存较小的一半一个最小堆存较大的一半。中位数就是两个堆顶之一或二者平均。class MedianFinder { private: priority_queueint left; // 大根堆存较小的一半堆顶是较小一半的最大值 priority_queueint, vectorint, greaterint right; // 小根堆存较大的一半堆顶是较大一半的最小值 public: void addNum(int num) { // 先插入左侧大根堆 if (left.empty() || num left.top()) left.push(num); else right.push(num); // 平衡左侧最多比右侧多1个 if (left.size() right.size() 1) { right.push(left.top()); left.pop(); } if (right.size() left.size()) { left.push(right.top()); right.pop(); } } double findMedian() { if (left.size() right.size()) return left.top(); return (left.top() right.top()) / 2.0; } };为什么左侧用大根堆、右侧用小根堆因为中位数恰好是“较小一半的最大值”和“较大一半的最小值”之间的分界。只要左侧堆顶小于等于右侧堆顶中位数就能从两个堆顶取得。这道题面试官会连环追问如果不要求实时查询只是给一个数组求中位数直接sort是O(n log n)双堆的优势在于每插入一个数O(log n)、查询O(1)。如果数据范围有限比如0到100之间的整数可以用计数数组插入O(1)、查询O(1)比双堆还快。如果数据量极大放不下内存可以分桶、先用外部排序等方案。双堆题的易错点是平衡逻辑。很多人喜欢先无脑插入再“一边倒”地调整思路没问题但平衡条件要写对。我用的约定是左侧数量要么等于右侧要么比右侧多1。这个约定让findMedian只需要判断一种情况代码最简洁。面试时先跟面试官说明这个约定再写代码逻辑清晰很多。3.4 23. 合并K个升序链表这是多路归并的代表题。K个升序链表最简单的做法是每次比较K个头结点取最小的时间复杂度O(nK)n是总节点数。用堆优化后每次从堆顶取最小节点O(log K)整体O(n log K)在K很大时优势明显。ListNode* mergeKLists(vectorListNode* lists) { auto cmp [](ListNode* a, ListNode* b) { return a-val b-val; }; priority_queueListNode*, vectorListNode*, decltype(cmp) pq(cmp); for (auto* head : lists) { if (head) pq.push(head); } ListNode* dummy new ListNode(0); ListNode* tail dummy; while (!pq.empty()) { auto cur pq.top(); pq.pop(); tail-next cur; tail cur; if (cur-next) pq.push(cur-next); } return dummy-next; }这个解法的一个精妙之处在于堆里只保存每个链表当前的头节点而不是保存所有节点。取走某个节点后再把它的next压入堆中。这样堆的大小始终不超过K空间复杂度O(K)。坑点有两个。第一个是空链表的处理初始化时就要把空链表跳过不然后面pq.top()会拿到空指针。第二个是比较器不要比较地址一定要比较a-val。我见过有人图省事直接把指针放进去默认比较指针大小运行结果完全错误还排查了半天。这道题的变体是“合并K个排序数组”“合并K个升序序列”思路完全一样。再往深层说这就是外部排序的核心思想当数据量大到内存放不下时把大文件拆成多个有序小文件再用多路归并合成一个有序大文件。面试如果聊到大数据排序你就可以拿这个例子来承接画风立刻不一样。3.5 1046. 最后一块石头的重量这道题属于堆的入门题但hot100里包含了它说明堆的标签在hot100里其实包含了从入门到进阶的跨度。题目一堆石头每次取两块最重的相互粉碎如果重量相同全碎否则剩余差值的石头放回求最后石头的重量。解法就是大根堆模拟int lastStoneWeight(vectorint stones) { priority_queueint pq(stones.begin(), stones.end()); while (pq.size() 1) { int a pq.top(); pq.pop(); int b pq.top(); pq.pop(); if (a ! b) pq.push(a - b); } return pq.empty() ? 0 : pq.top(); }思路一句话每次取两个最大值模拟粉碎过程。这题的难点完全不在算法而在理解“为什么用堆最合适”——因为题目每次需要动态获取最大值并且取走最大值后还会有新元素插入这种“边取边加”的场景恰好是堆的使用场景。如果用贪心排序每次重新排序的成本太高。顺带一提这题也是一个很好的“读题能力”考察点。面试官期待的是你从题目里提取出“动态取最大”这个关键需求。你可以练习着把这类描述都转译成数据结构需求的句式比如“每次取最大/最小且伴随插入”就等于“堆”。3.6 378. 有序矩阵中第K小的元素这道题的矩阵每一行、每一列都非严格递增让你找第K小的元素。两种主流解法一是多路归并堆二是二分答案。堆的做法类似合并K个有序序列把每一行的第一个元素预先放入堆里每次弹出最小再将该行下一列的元素入堆弹出K次即可int kthSmallest(vectorvectorint matrix, int k) { int n matrix.size(); auto cmp [](const pairint, int a, const pairint, int b) { return matrix[a.first][a.second] matrix[b.first][b.second]; }; priority_queuepairint, int, vectorpairint, int, decltype(cmp) pq(cmp); for (int i 0; i n; i) { pq.push({i, 0}); } int res 0; while (k-- 0) { auto [r, c] pq.top(); pq.pop(); res matrix[r][c]; if (c 1 n) pq.push({r, c 1}); } return res; }时间复杂度O(k log n)当k接近n^2时会退化为O(n^2 log n)但实际题目k一般不大。另一种二分答案法是O(n log(max-min))在k很大的时候更稳定。两种方法面试都值得掌握我个人的建议是优先掌握堆方法因为和多路归并是同一个套路好记如果时间充裕再学二分解法作为“进阶方案”备用。4. 面试现场的经验心得关于堆的本质认知4.1 堆和栈的误区别再被“堆栈”两个字绕晕热词里有人搜“堆和栈”这其实是两个层次的混淆。在算法题里堆和栈是两种完全不同的数据结构一个是完全二叉树一个是线性表在程序运行内存里堆是动态内存分配区栈是函数调用栈。两个维度千万不要混在一起。很多初学者问栈不也能O(1)取最大值吗不是普通栈O(1)只能取尾元素如果你维护一个单调栈确实可以在O(1)取某个方向上的极值但单调栈只能解决“一次性扫描”的问题插入一个新元素时单调栈需要弹出大量元素摊还分析下很多场景仍然O(n)。而堆的核心优势是每次插入、删除都是严格的O(log n)适合反复动态变化的场景。一句话总结如果你需要在一堆不断增删的数据里反复取极值用堆如果只需要在静态序列上扫描一次维护一个单调的窗口用单调栈/单调队列更合适。这个区分在面试里非常常见务必想清楚。4.2 TopK问题堆和快速选择的取舍TopK是堆最重要的应用场景但堆不是唯一解法。我在面试中会先给出堆解法然后跟面试官讨论三种方案方案时间复杂度空间复杂度适用场景排序O(n log n)O(1)数据量小需要全部有序堆O(n log K)O(K)数据量大K远小于n适合流式数据快速选择平均O(n)O(1)数据一次性给定不需要动态插入这里有个容易被忽略的点堆特别适合流式数据。如果数据是一个一个到来的你没法一次性排序也没法做快速选择只能用堆维护当前TopK。这是堆的不可替代性也是面试官最想听到的理解。4.3 C优先队列的自定义比较器方向陷阱详解这一段是很多人的痛点我必须展开写。C的priority_queue比较器语义和sort完全不同这导致无数人翻车。reduce到一句话priority_queue的比较器返回true时表示第一个元素排在第二个元素后面优先级更低所以它实际上定义的是弱序中的“优先级关系”而不是“排序关系”。priority_queueint默认是大根堆因为默认比较器lessinta b返回true时表示a排在后面所以较大的数优先级更高。priority_queueint, vectorint, greaterint是小根堆因为a b返回true时表示a排在后面所以较小的数优先级更高。如果你用lambda自定义想创建小根堆需要写auto cmp [](int a, int b) { return a b; // 注意是 不是 }; priority_queueint, vectorint, decltype(cmp) pq(cmp);a b返回true表示a位于b之后a的优先级更低所以小的数在堆顶。这个写法看起来像反的但实际上完全正确。最好的自检方法是往堆里push三个数打印堆顶看是不是你期望的极值。Python用户会舒服很多heapq默认就是小根堆计算第K大时只需要用-x入堆技巧即可。Java的PriorityQueue默认也是小根堆。只有C需要额外注意这个坑。4.4 堆和快排结合找前K个高频单词的进阶思考hot100里没有收录“前K个高频单词”但它是347的一个重要变体面试中经常出现。它要求频率降序、同频率按字典序升序。用堆的时候比较器会变得很微妙你需要在堆里实现“频率少优先弹出、同频率字典序大的优先弹出”这样堆里剩下的才是正确答案。用C自定义比较器auto cmp [](pairstring, int a, pairstring, int b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; };这里的逻辑是频率小的优先级低同等频率下字典序大的优先级低这样留在堆里的就是频率大且字典序小的单词。换句话说你要反过来想——堆在弹出时淘汰谁剩下的就是你要的答案。这个思考方式对TopK变体题特别管用。5. 工程场景里的“堆”不只是刷题5.1 从TopK到海量数据堆在外排序中的角色很多人觉得堆只是面试用的实际工作中用不到。其实堆在工程里的应用相当广泛最常见的场景就是海量数据的排序与归并。举个例子你有一份几百GB的日志文件机器的内存只有几GB怎么排序标准做法是外部排序把大文件切分成多个可以载入内存的小块每一块内部用快速排序排好然后维护一个大小为“文件路数”的小根堆每次从堆顶取最小元素写入输出文件再从对应的块中补充下一个元素。这就是堆的多路归并在工程中最为典型的一个落地。它的核心价值在于内存里只需要保存每路当前的最小值不需要把整个数据载入内存。理解了这个场景再回头看23题合并K个升序链表你会觉得它不是一个孤立的题目而是在模拟真实世界的数据处理过程。再比如常见的求日活Top10榜单、热卖商品Top100这类场景的本质也是流式TopK。数据一条一条地来内存有限不能存全量数据那你只能维护一个大小为K的小根堆。这就是堆算法在海量数据场景下最直接的应用。5.2 一个容易被忽略的细节优先队列与“懒删除”在实际编码中优先队列删除任意一个元素是很麻烦的因为堆只支持删除堆顶。那如果业务上有需求要删除一个不在堆顶的元素怎么办比如在一个动态榜单里某个商品的分数变了需要在堆里更新它的位置。常见的做法是懒删除你并不立刻在堆中删除该元素而是再插入一个新元素表示新状态被淘汰的旧状态后面弹出堆顶时再检查是否为垃圾数据是的话直接跳过。这个技巧在不支持任意删除的语言环境中非常实用。配合一个unordered_map记录每个元素当前的有效状态即可。刷题虽然不需要频繁用懒删除但理解它有助于你看懂很多开源的定时器实现、任务调度器实现。堆懒删除的组合在工程里出现频率极高。5.3 提醒编译器的堆空间不足与内存维度的“堆”热词里出现了“编译器的堆空间不足”这跟算法题里讨论的数据结构堆不是一个东西但在面试的角落里可能会交汇。内存维度的堆是动态分配内存的区域使用new/malloc分配的内存都放在这里如果不释放长期运行的程序就会遇到“内存溢出”“堆空间不足”。在刷题场景下偶尔也会遇到类似问题递归太深导致栈溢出或者一次性把超大数组塞进内存导致堆溢出。后者通常不是因为程序写错了而是算法空间复杂度太高。举个例子如果你用排序解决第K大问题空间是O(n)用堆解决则是O(k)。当n是千万级别时O(k)的方案可能内存占用只有几MBO(n)的方案可能直接爆掉。所以“为什么这个题要用堆”很多时候不只是为了时间复杂度更是为了空间复杂度。这个角度面试中值得主动提出来因为它展现了你对资源消耗的敏感度。6. 常见问题与排查技巧实录6.1 堆题调试三板斧边界、比较器、空指针堆题的bug其实高度集中我把踩过的坑总结成一份排查清单每次WA或者RE按顺序检查这三样第一边界条件。第K大问题里K是否等于1或等于n堆的大小变化是否符合预期数据流中位数里第一次插入时两个堆都为空代码会不会崩溃合并K个链表时所有链表都是空的dummy节点能不能正确返回空第二比较器方向。C自定义比较器的方向对不对你是否用完sort的习惯误写了堆里存的是pair比较的是first还是second很多TopK变体题pair的两个字段一个要升序一个要降序细节极多。第三空指针与空容器。弹出堆顶之前检查空了吗链表题的dummy节点处理了吗矩阵题的行索引、列索引会不会越界这些错误有个共同特征编译不报错、逻辑跑起来偶尔错特别难排查。6.2 数据流中位数双堆平衡条件的调试心得双堆题是我见过初学者最容易写乱的一道。常见错误是插入逻辑和平衡逻辑混在一起最后两个堆的大小要么差太多要么堆顶关系错误左侧堆顶大于右侧堆顶。我的调试建议是写一个辅助函数来验证堆的性质bool isValid() { if (left.size() right.size()) return false; if (left.size() right.size() 1) return false; if (left.empty() || right.empty()) return true; return left.top() right.top(); }每次addNum之后调用它返回false就说明平衡逻辑写错了。这个辅助函数同样适用于面试现场它可以让面试官立刻明白你对自己代码的正确性是有把握的而不是写完就草草了事。6.3 堆排序手写题面试官到底想看什么有时候面试官不问你堆题而是直接让你手写堆排序。这其实是对堆理解的终极考验。我建议按照“建堆 反复交换堆顶与末尾”这个框架来写void heapSort(vectorint a) { int n a.size(); // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) { down(a, i, n); } // 依次取出堆顶放到末尾 for (int i n - 1; i 0; i--) { swap(a[0], a[i]); down(a, 0, i); } }这里最容易被问的是“建堆为什么从n/2-1开始”因为n/2-1是最后一个非叶子节点的下标叶子节点没有孩子不需要下沉。整个建堆的时间复杂度是O(n)不是O(n log n)这一点很多人会算错。推导思路是各层节点数乘以它的高度求和最后收敛为一个常数倍的n。堆排序不是稳定的排序算法这是一个高频考点。原因是堆调整过程中值相同的元素可能在数组中做跨越式移动打破原有顺序。面试答到这里基本可以收尾了。7. 刷题顺序建议与小技巧分享如果你正准备刷hot100的堆题我建议按下面的顺序来难度阶梯比较合理最后一块石头的重量——堆的入门熟悉API数组中的第K个最大元素——掌握TopK套路前K个高频元素——哈希堆配合理解pair比较器合并K个升序链表——多路归并队列中存指针数据流的中位数——双堆进阶动态维护有序矩阵中第K小的元素——多路归并变体顺便学二分每做完一道我建议你追问自己三个问题这道题如果不用堆还能怎么做复杂度差在哪里如果数据是不断流入的流式哪种方案仍然可用把这三个问题的答案写在这道题旁边会形成你自己的“堆题方法论”。我到后来回顾发现自己面试时能快速反应出最佳方案靠的就是这种整理而不是盲目刷得多。另一个小技巧是把每一道堆题的“比较器”单独抽出来练习。因为堆题一半的难度在比较器上而比较器又能通用到其他题里。比如把347的pair比较器改一改就是前K个高频单词的解法把23的节点比较器改成数组下标比较就是合并K个排序数组的解法。练熟比较器等于一次掌握五六道题。我个人还有一个习惯一题三写。同一道题用C的priority_queue写一遍用Python的heapq写一遍再手写一份数组堆模拟。前两种帮你熟悉工业级API后一种帮你理解堆的底层。三种写过之后这道题的理解深度完全不一样。最后再分享一个小技巧在笔试或者白板面试那种紧张环境下堆题最忌讳的就是一上来就写代码。先花几秒钟大声说出你选的堆类型、性质、以及堆中元素代表什么含义。比如“我用一个小根堆维护当前最大的K个元素堆顶就是第K大的”。这句话说完你的思路已经固定代码基本不会跑偏。这个“先说后写”的习惯尤其适合堆这种边界条件多、比较器容易写反的题型能帮你少踩至少一半的坑。
