★ FEATURED ARTICLE 说实话力扣 hot 100 里的堆篇很容易被划过去。很多人一看到“堆”就头大觉得概念抽象、代码难写还不如直接排序来得省事。但等你真把这几道题刷完就会发现堆在整个 hot 100 里扮演的角色其实非常固定它是处理“动态取最值”、“Top-K”这类问题的一把钥匙而且实现复杂度远没有想象的那么高。今天想把这部分拆开揉碎来讲按我的经验你只要吃透 215、347、295、23 这四道题堆相关的面试题基本就稳了。这篇文章的目标读者就是那些刚刷到“堆”标签、想用一个晚上把 hot 100 堆题全部搞定的同学也欢迎已经在排序、链表题里打过滚、想换个姿势理解数据结构的选手。1. 堆题先搞清“堆到底是什么”1.1 堆是数据结构不是内存区域先澄清一个经常被绕晕的点力扣里说的“堆”和操作系统里“堆内存”“堆空间不足”不是一回事。前者是数据结构 heap适合用来动态维护集合里的最大值或最小值后者是进程运行时动态分配内存的存储区域。面试时两者都叫 heap但完全是两条知识线别混在一起。堆的底层理论上是一棵完全二叉树但真正写代码的时候它根本不需要像二叉树那样用 node 和指针串起来而是直接存在数组里。假设当前节点下标是 i那么它的左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。这个特性意味着我们只需要对一个普通 Python 列表做操作就能维持堆结构。堆的核心性质只有一条对于小顶堆任意节点的值不大于它的左右孩子所以根节点永远是全堆最小的大顶堆则反过来根节点是最大的。注意堆只保证根和父子之间的顺序不保证兄弟节点之间有大小关系这决定了它和“排序”有本质区别——堆偏向于“快速找到最值”而不是把整个序列排整齐。1.2 Python 的 heapq 就是你想要的现成轮子Python 标准库里的 heapq 模块已经实现了基于列表的堆操作不用自己从头写 shift up、shift down。日常刷题最常用的有这几个heapq.heapify(heap)将普通列表原地堆化时间复杂度 O(n)这个操作比想象中快因为用的是下沉法而非逐个插入heapq.heappush(heap, item)插入元素O(logn)heapq.heappop(heap)弹出并返回堆顶O(logn)heapq.heapreplace(heap, item)先弹出堆顶再插入新元素O(logn)比先 pop 再 push 快一点heapq.heappushpop(heap, item)先插入再弹出堆顶适合“如果比堆顶大才需要替换”这种场景heapq.nlargest(n, iterable)/heapq.nsmallest(n, iterable)直接返回前 n 个大或小的元素内部依然用堆实现适合做结果校验。还要注意heapq 只支持小顶堆官方没有直接提供大顶堆。想要大顶堆最常见也最优雅的做法是把元素取负再入堆取出时再取负还原。这个操作后面会反复出现建议现在就内化成肌肉记忆。1.3 大小顶堆和“比较规则”的关系有些同学会问我往堆里放的如果是 (0, 3) 这种元组堆按什么规则比较答案是元组从左往右逐项比较第一个元素分出大小就停止否则继续比第二个。所以当你需要“按频率堆化频率相同再按字典序排”时就需要有意控制元组每一项的顺序。刷 hot 100 堆题不需要用自定义类那通常出现在更复杂的场景。这里给你一个通用结论如果堆元素是元组第一项永远是排序的主键如果第一项相同才会看第二项。理解了这一点后面 347、295 的代码就自然读懂了。2. 力扣 hot 100 堆题逐个击破2.1 215. 数组中的第K个最大元素题目是给一个未排序数组找出第 K 大的元素。所有堆题里这道是最基础的因为它的解法足够套路化。先说思路维护一个大小为 K 的最小堆。遍历全部元素时先把前 K 个塞进去之后每遇到一个新元素就和堆顶当前堆里最小的那个比较如果新元素更大就用heapreplace把它替换进堆。遍历完成后堆顶就是整个数组里第 K 大的元素。为什么堆顶是第 K 大因为堆里永远保留着“到目前为止最大的那 K 个数”而堆顶是这 K 个数里最小的也就是全局第 K 大。class Solution: def findKthLargest(self, nums: List[int], k: int) - int: heap [] for x in nums: if len(heap) k: heapq.heappush(heap, x) elif x heap[0]: heapq.heapreplace(heap, x) return heap[0]这个代码很短但背后有两个关键点。第一个关键点是为什么用“最小堆”找“最大”。如果你直觉上用一个最大堆往里弹 K 次才能拿到答案复杂度变成 O(Klogn)K 接近 n 时就是 O(nlogn)而维护大小为 K 的小顶堆复杂度是 O(nlogK)而且内存占用只有 O(K)适合数据流很大的情况。第二个关键点是heapreplace和“先 pop 再 push”的区别前者一次完成替换少了一次堆化操作在频繁触发替换时性能更稳。如果不满足于 O(nlogK)这道题还有快速选择的写法按照快排分区的思路随机选中轴把大于中轴的放左边或按题目定义然后根据分界点位置判断第 K 大在哪个区间平均 O(n)但最坏 O(n^2)。面试时我建议先写堆方案作为保底再提快选思路这样既稳妥又显深度。2.2 347. 前K个高频元素这道题是“哈希表计数 堆求前 K”的组合拳也是 hot 100 里堆篇最典型的套路之一。第一步遍历数组用Counter统计每个数字出现的次数这一步 O(n)。第二步维护一个小顶堆堆元素是(count, num)这样的元组只保留频率最高的 K 个。为什么元组要把 count 放在第一项因为堆比较时先看第一项这样堆顶永远是当前堆里“频率最低”的元素。如果 num 放在第一项堆就按数字大小排列计数完全失灵题目直接做不出来。这个细节是高频考点也是新手最容易写反的地方。class Solution: def topKFrequent(self, nums: List[int], k: int) - List[int]: cnt Counter(nums) heap [] for num, freq in cnt.items(): if len(heap) k: heapq.heappush(heap, (freq, num)) elif freq heap[0][0]: heapq.heapreplace(heap, (freq, num)) return [num for _, num in heap]如果要求前 K 个高频元素按频率从高到低输出你可以最后对 heap 排序再翻转如果不要求顺序直接返回即可。这里还有一个很实用的偷懒方案heapq.nlargest(k, cnt.items(), keylambda x: x[1])一行搞定但内部仍是堆只是把比较逻辑通过 key 指定了。实际上刷题和面试中手写上面这种显式堆反而更能体现你理解本质。扩展一点如果把题目改成“前 K 个高频单词”并且要求频率相同按字典序升序元组可以写成(-freq, word)。把 freq 取负小顶堆就变成了“按频率从高到低”的堆同时字典序默认升序刚好满足题目要求。这是 692 题的解法也是 347 最自然的延伸。2.3 295. 数据流的中位数这道题的经典解法是“对顶堆”一个大顶堆维护数据流较小的一半一个小顶堆维护较大的一半两个堆的堆顶合起来就能得到中位数。具体来说定义left为大顶堆用负数模拟存放较小的一半定义right为小顶堆存放较大的一半。保证两个堆的大小之差不超过 1且 left 中的所有元素都小于等于 right 中的所有元素。插入新元素时为了维护这个顺序我先把它放进 left再把 left 的最大值弹出来塞进 right。如果此时 right 比 left 多就把 right 的最小值塞回 left。这样保证 left 要么和 right 一样大要么多一个元素。查询中位数时如果 left 多一个元素left 堆顶就是中位数否则中位数是 (left 堆顶 right 堆顶) / 2。class MedianFinder: def __init__(self): self.left [] # 大顶堆存负数 self.right [] # 小顶堆 def addNum(self, num: int) - None: heapq.heappush(self.left, -num) heapq.heappush(self.right, -heapq.heappop(self.left)) if len(self.right) len(self.left): heapq.heappush(self.left, -heapq.heappop(self.right)) def findMedian(self) - float: if len(self.left) len(self.right): return -self.left[0] return (-self.left[0] self.right[0]) / 2这段代码最妙的地方是那个“先加入 left再弹出给 right”的流程它天然保证了 left 里所有元素都小于 right。如果在实际题目里出现重复元素也不怕堆允许重复值堆排序本来就不是稳定排序这里也不需要稳定。每次 addNum 触发常数次堆操作复杂度 O(logn)findMedian 是 O(1)。这个数据结构的名字叫“对顶堆”它不只是为这道题服务后面做 480. 滑动窗口中位数就是 295 加了一个删除窗口元素的机制同样沿用这套思路。2.4 23. 合并K个升序链表hot 100 的堆标签里这道题经常被安排在链表部分但因为它的最优解法是堆所以堆篇也必须讲。题目给 K 个升序链表要求把它们合并成一个升序链表。思路非常直接把所有链表的头节点放进一个小顶堆堆里元素是 (val, idx, node)。每次弹出堆顶节点把它接到结果链表末尾然后如果这个节点还有下一个节点就把下一个节点入堆。因为每个链表都是升序的当前堆顶一定是所有链表头节点里最小的所以这个过程产生的链表整体有序。idx 的作用是防止两个节点的 val 相等时Python 去比较第三个元素 node而 ListNode 对象本身不支持比较会直接报错。class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: heap [] for i, l in enumerate(lists): if l: heapq.heappush(heap, (l.val, i, l)) dummy ListNode(0) cur dummy while heap: val, i, node heapq.heappop(heap) cur.next node cur cur.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next这个解法的复杂度是 O(NlogK)N 是所有节点总数K 是链表条数。之所以用堆而不是每次遍历 K 个头节点找最小值是因为 K 一旦变大遍历的成本是 O(K)堆能把单次取最小值降到 O(logK)。如果你用“两两合并”的思路每次合并两个链表都要重新扫描总体复杂度会高不少。3. 堆题的高频套路与延伸3.1 Top-K 模板一套代码吃透所有变体把 215 和 347 放到一起看你会发现它们本质上是同一个模板维护大小为 K 的堆遍历所有元素只保留符合条件的 K 个。区别只在于堆的大小、比较的键、以及最终要返回堆顶还是整个堆。我习惯把模板写成这样def top_k(iterable, k, key_func, is_largestTrue): heap [] for item in iterable: key key_func(item) if len(heap) k: heapq.heappush(heap, (-key if is_largest else key, item)) else: # 如果要求最大 K 个用小顶堆要求最小 K 个用大顶堆 if is_largest and key -heap[0][0]: heapq.heapreplace(heap, (-key, item)) elif not is_largest and key heap[0][0]: heapq.heapreplace(heap, (key, item)) return [item for _, item in heap]这里有个常见的误区很多新手会下意识地认为“找最大 K 个应该用最大堆”但正确的做法恰恰相反找最大的 K 个元素要维护一个小顶堆让最小的那个在堆顶随时准备被更大的新元素挤掉只有当堆顶是最小的我们才能用一个 O(1) 的比较判断新元素有没有资格进入 Top-K。这个反直觉的设计是 Top-K 问题最核心的点想清楚它你就不会再背错方案了。3.2 对顶堆与“流式数据”场景295 的对顶堆套路核心价值在于它天然适合流式场景。数据不是一次性全部给出也不是存在数组里可以被随机访问而是一点一点地来。这时候排序做不到每次插入都 O(n)二叉搜索树和红黑树也能做但实现复杂度高对顶堆用两个标准库的堆操作就搞定了。Google、字节这种喜欢考系统设计的公司经常把 295 包装成“如何计算股票每隔几秒的实时中位数”底层逻辑完全一样。所以我建议把 295 的代码背下来面试时可以直接默写。3.3 堆和排序面试时怎么选这四道题刷完你应该能总结出一条经验当数据量小且固定直接排序往往比堆更简单比如求一个静态数组的中位数排序后取中间值就是最优答案但数据要是流动的、动态的或者 K 远小于 n堆就是更合适的选择。场景排序方案堆方案一次性求静态 Top-KO(nlogn)代码最直观O(nlogK)内存更优数据流动态求中位数每次插入排序 O(n)对顶堆 O(logn)合并 K 个有序序列两两合并 O(NK)堆 O(NlogK)需要频繁弹出最小元素不适用直接 heappop4. 堆题调试方法与常见坑4.1 新手必踩的五个坑第一个坑是用 heapq 却忘了它只有小顶堆。一上来直接对大顶堆的需求调用 heappop结果取到的是最小值查半天不知道错在哪。第二个坑是元组比较陷阱。堆里放 (val, node) 时如果两个 val 相等Python 就会比较 node而 ListNode 类型不支持比较直接抛TypeError: not supported between instances of ListNode and ListNode。修复方法就是加一个不会重复的下标比如 (val, idx, node)。第三个坑是试图直接修改堆里的元素。heapq 不做动态更新如果你改了堆里某个值堆的性质就被破坏了后续 heappop 可能返回错误结果。这种情况需要“懒删除”用一个计数器标记哪些元素已经失效弹出时跳过无效值即可复杂度仍然是 O(logn)。第四个坑是空堆调用堆顶。pop 之前一定要判断堆是否为空尤其在使用堆处理条件分支时稍不注意就 IndexError。第五个坑是我见过最多的把频次和元素本身的前后顺序写反。堆元素 (num, count) 而不是 (count, num)结果堆完全按 num 排序了题目怎么跑都是错。建议每次写堆之前先在注释里写出“第一项是排序键”。4.2 调试技巧小数据多打印之前我在刷 295 时最开始写出的代码在 addNum 次数少于 3 时会出错就是因为没耐心去打印两个堆的内容。建议你在本地调试时额外写一个 debug 方法把 left 的取负原值打印出来并且每次 addNum 后检查两个堆的长度差值是否超过 1。二分搜索和很多树题可以静态分析但堆题特别适合“打印堆顶”来判断状态有没有维护好。另外可以用heapq.nlargest做对拍。例如在本地随机生成一个数组先排序取第 K 大再用你的堆解法跑一遍两个答案不一致就能立刻定位问题。这种做法在刷题初期看起来慢但能帮你建立对堆行为的直觉后面写更复杂题目会省很多时间。4.3 性能细节与关键选择虽然 O(nlogK) 和 O(nlogn) 在力扣的数据量下可能都是几百毫秒但要注意堆操作的常数因子其实不小。如果你发现代码在超大数组上超时可以看看是不是用了“先 heappush 再 heappop”的组合改成heappushpop或heapreplace后性能会有明显提升。还有一种常见优化是提前用 heapify 对数组原地建堆而不是一个一个 push前者 O(n)后者 O(nlogn)。5. 从零安排 hot 100 堆篇的刷题路线与建议先说一个个人很受用的观点堆题不要贪多hot 100 里合适的题目就那几道重点是把每一道题背后的“为什么”吃透。我的建议顺序是 215 - 347 - 295 - 23大致可以分成两个晚上或者一个完整的下午。第一晚搞定 215 和 347。215 让你掌握最核心的“大小为 K 的堆”模板347 让你学会“哈希计数 堆”的组合。这两道题做完你至少能对付 80% 的 Top-K 类问题。第二晚专门啃 295先看对顶堆代码然后手动模拟几组数据体会两个堆如何互相配合。最后再做 23把堆放进链表场景里验证自己的理解。做 295 时最容易出现的问题是“看得懂、写不出”。建议你把代码遮住在纸上画出 [1, 2, 3, 4, 5] 五个数依次插入对顶堆后两个堆的状态模拟完一遍再动手写比直接抄代码有效得多。23 题则要注意链表指针的交接建议画一下 dummy - node1 - node2 的链式结构别被“链表 堆”两个概念同时夹击。我个人习惯在刷堆题时准备一个小本子每道题只记录三件事堆的 size 是多少、堆里元素的比较键是什么、最后返回的是堆顶还是整个堆。做完 hot 100 这四道题翻一翻这本子你会发现自己已经能非常快地识别出“这道题其实就是用堆维护前 K 大”这种本质而不是被题目表面的包装吓得绕路。如果后面想继续加深可以顺手把 692. 前K个高频单词、373. 查找和最小的K对数字、378. 有序矩阵中第K小的元素这些变体也刷一遍核心套路完全一样算是白赚的熟练度。
阅读完成 · 觉得有帮助？
