堆有哪些典型应用？（合并 K 个有序链表、Dijkstra、定时任务等）
简化版
堆/优先队列的核心能力是「反复高效地取出最值」，凡是需要这个的场景都用它：Top K 与第 K 大、合并 K 个有序链表/数组（小顶堆取各路最小）、Dijkstra 最短路 / Prim 最小生成树（取当前距离最小的点）、定时任务 / 延迟队列（取最早到期的任务）、哈夫曼编码（反复取两个最小频率合并）、数据流中位数（对顶堆）。
详细版
| 应用 | 用堆做什么 | 用哪种堆 |
|---|---|---|
| Top K / 第 K 大 | 维护 size K 的堆淘汰 | 求最大用小顶堆 |
| 合并 K 个有序链表/数组 | 每次取 K 路中最小的头 | 小顶堆 |
| Dijkstra 最短路 | 每次取当前距离最小的节点 | 小顶堆 |
| Prim 最小生成树 | 每次取权最小的边 | 小顶堆 |
| 定时任务 / 延迟队列 | 取最早到期的任务 | 按到期时间的小顶堆 |
| 哈夫曼编码 | 反复取两个频率最小的节点合并 | 小顶堆 |
| 数据流中位数 | 对顶双堆维护两半 | 大顶堆 + 小顶堆 |
完整版教学
一、堆的「能力画像」
判断一个问题能不能用堆，就问一句：它是不是需要「不断地、动态地取出当前最大或最小的元素」？ 如果是，堆几乎总是最优工具——O(1) 看极值、O(log n) 取极值、还能一边取一边加新元素。下面这些经典应用，本质都是这个能力的不同包装。
二、合并 K 个有序链表
把 K 个有序链表合成一个有序链表。用小顶堆装「每个链表当前的头节点」（共 K 个），每次弹出堆里最小的接到结果后面，再把它的下一个节点入堆。
- 堆大小始终 ≤ K，每次操作 O(log K)。
- 总共 N 个节点，每个进出堆一次，总复杂度 O(N log K)。
这比「两两合并」更优雅，是优先队列的经典应用。合并 K 个有序数组同理。
三、Dijkstra 最短路 / Prim 最小生成树
- Dijkstra：求单源最短路。用小顶堆存「待处理节点及其当前最短距离」，每次取出距离最小的节点去松弛它的邻居。堆让「找当前最近的未处理节点」从 O(V) 降到 O(log V)，整体优化到 O(E log V)。
- Prim：求最小生成树，思路几乎一样——用小顶堆每次取「连接树与非树的最小权边」。
「每次取当前代价最小的往前走」是贪心 + 堆的经典组合。
四、定时任务 / 延迟队列
任务带「执行时间」，要总能拿到最早该执行的那个。用一个按到期时间排序的小顶堆：堆顶就是下一个要触发的任务。
- Java 的
DelayQueue、Timer/ScheduledThreadPoolExecutor内部都用这种「时间堆」（最小堆）。 - 定时器不断看堆顶：到期就弹出执行，没到期就睡到堆顶的时间。
五、哈夫曼编码
构造哈夫曼树做数据压缩：用小顶堆装所有字符节点（按频率）。反复取出两个频率最小的节点，合并成一个新节点（频率相加）再放回堆，直到只剩一个——就是哈夫曼树的根。每次「取两个最小」正是堆的拿手好戏。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| Top K | 只维护 K 个候选，降低排序成本 |
| 合并 K 路 | 每次取当前最小头节点 |
| Dijkstra/Prim | 快速取当前最小距离或最小边 |
| 定时任务 | 按最近触发时间取任务 |
heap ability:
offer(x): O(log n)
poll best: O(log n)
peek best: O(1)
best = min or max by comparator堆适合的问题都有同一个味道：反复从动态集合里取当前最优元素。
- 误区：堆适合快速查任意元素。 堆只保证堆顶最优，不支持像哈希表那样 O(1) 找任意元素。
- 误区：合并 K 个链表要把所有节点一次性放入堆。 更优做法是每条链先放头节点，每弹出一个再放它的下一个，堆大小维持 K。
- 误区：Dijkstra 用普通队列也一样。 带权非负图需要每次取当前距离最小的点，优先队列才能保证贪心顺序。
- 追问：定时任务为什么用小顶堆？ 堆顶就是最近要执行的时间，调度器只需看堆顶是否到期。
- 追问：哈夫曼编码为什么用堆？ 每轮都要取两个最小权重节点合并，小顶堆正好支持动态取最小。
- 追问：什么时候不该用堆？ 需要有序遍历、范围查询或删除任意元素时，平衡树或其他结构通常更合适。
七、加强记忆
堆的能力是「动态反复取最值」，凡需此皆可用：Top K（size K 堆）、合并 K 个有序链表（小顶堆取各路最小，O(N log K)）、Dijkstra/Prim（小顶堆取当前最小距离/权）、定时任务/延迟队列（时间小顶堆取最早到期，如 Java DelayQueue）、哈夫曼编码（反复取两个最小频率合并）、数据流中位数（对顶双堆）。判断能否用堆就问：是否需要不断取当前最大/最小。