堆题解：优先队列弹出的，是当前最值得处理的候选

堆题解优先队列弹出的是当前最值得处理的候选一、堆不是排序的廉价替代品优先队列在算法题里很常见。Top K、合并有序链表、Dijkstra、任务调度都能见到它。但很多题解会把堆简单解释成“每次取最大或最小”。这只说了表面。堆的真正价值是维护一批候选并保证每次取出当前最值得处理的那个。如果只是把所有元素排序一次后续没有动态加入候选堆未必必要。堆适合候选集合会变化的场景。二、堆维护的是动态候选集以合并 k 个有序链表为例每次弹出当前最小节点再把它的下一个节点加入候选。flowchart TD A[初始化每个链表头节点] -- B[加入小根堆] B -- C[弹出当前最小] C -- D[接到结果链表] D -- E{是否有 next} E --|有| F[next 入堆] F -- C E --|无| C堆里从来不需要放所有节点只放每条链当前最小的候选。三、Python heapq 示例Python 的 heapq 是小根堆。节点值相同时要加一个序号避免对象不可比较。import heapq def push_node(heap, idx, node): if node is not None: heapq.heappush(heap, (node.val, idx, node))面试时要说清楚为什么加 idx。不是为了装饰而是避免两个节点值相同时比较 node 对象报错。四、复杂度要按入堆次数算合并 k 个链表总节点数 n每个节点最多入堆一次、出堆一次堆大小最多 k所以复杂度是 O(n log k)。不要写成 O(n log n)那说明候选集大小没理解。Top K 高频题也类似。维护大小为 k 的小根堆遍历 n 个元素复杂度 O(n log k)。如果 k 接近 n排序可能更简单。算法选择要看约束不要盲目上堆。最后Dijkstra 里堆可能有过期节点。弹出时要判断当前距离是否仍然可信。堆不会自动删除旧候选代码要自己处理。堆也常用于“第 k 个”问题。思路要看 k 和 n 的关系。k 很小维护大小为 k 的堆很合适k 很大可能排序更简单。算法不是越复杂越好约束决定工具。自定义比较器也要小心。优先级相同怎么办是否需要稳定顺序Python 里对象不能比较Java 里比较器写成a - b可能溢出。堆题的 bug 经常藏在比较器里。最后堆不能快速删除任意元素。需要删除中间元素时要么懒删除要么换数据结构。不要把优先队列当成万能有序集合。懒删除要有额外标记。比如滑动窗口中位数用两个堆维护时离开窗口的元素可能还在堆里。弹出堆顶时发现它已过期再继续弹。这种策略能保持复杂度但代码要小心同步计数。堆题也要注意空间复杂度。Top K 小根堆空间是 O(k)合并链表堆空间是 O(k)Dijkstra 堆里可能有多个候选最坏可以到 O(E)。复杂度分析不能只写时间不写空间。最后堆的“不稳定”有时会影响输出顺序。题目如果要求相同优先级按原顺序返回就必须额外保存序号。堆只保证优先级不保证你脑补的顺序。工程场景里堆常被拿来做定时任务调度。堆顶是最近要执行的任务执行后再把下一次触发时间放回堆里。这个例子能帮助理解堆维护的是“当前最早该处理”的候选而不是把所有任务排成永久顺序。如果题目需要同时拿最大值和最小值一个堆通常不够。可以用两个堆配合懒删除也可以考虑平衡树。先看操作需求再选数据结构。只会小根堆和大根堆互转还不算真正会用堆。五、总结堆适合维护动态候选集。每次弹出的不是“最神奇的元素”而是当前最值得处理的候选。复杂度要按堆大小和入堆次数分析。理解候选集才能知道什么时候该用堆什么时候排序就够了。