企业官网建设流程全解析

说实话，力扣 hot 100 里的堆篇很容易被划过去。很多人一看到“堆”就头大，觉得概念抽象、代码难写，还不如直接排序来得省事。但等你真把这几道题刷完就会发现，堆在整个 hot 100 里扮演的角色其实非常固定：它是处理“动态取最值”、“Top-K”这类问题的一把钥匙，而且实现复杂度远没有想象的那么高。今天想把这部分拆开揉碎来讲，按我的经验，你只要吃透 215、347、295、23 这四道题，堆相关的面试题基本就稳了。这篇文章的目标读者，就是那些刚刷到“堆”标签、想用一个晚上把 hot 100 堆题全部搞定的同学，也欢迎已经在排序、链表题里打过滚、想换个姿势理解数据结构的选手。

1. 堆题先搞清“堆到底是什么”

1.1 堆是数据结构，不是内存区域

先澄清一个经常被绕晕的点：力扣里说的“堆”和操作系统里“堆内存”“堆空间不足”不是一回事。前者是数据结构 heap，适合用来动态维护集合里的最大值或最小值；后者是进程运行时动态分配内存的存储区域。面试时两者都叫 heap，但完全是两条知识线，别混在一起。

堆的底层理论上是一棵完全二叉树，但真正写代码的时候，它根本不需要像二叉树那样用 node 和指针串起来，而是直接存在数组里。假设当前节点下标是 i，那么它的左孩子是 2i+1，右孩子是 2i+2，父节点是 (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(), key=lambda 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_largest=True): 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，堆就是更合适的选择。

4. 堆题调试方法与常见坑

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小的元素这些变体也刷一遍，核心套路完全一样，算是白赚的熟练度。