算法面试突击手册 —— 堆（优先队列）
一、概念与特点
大白话 + 类比
堆 = 急诊室分诊台
急诊室不按先来后到排队，而是按病情严重程度。护士（堆）不断接收病人，每次叫号（poll）都叫最危急的那个。新来的病人如果特别严重，会被排到前面。
- 小根堆（最小堆）：堆顶是最小元素，越小的优先级越高
- 大根堆（最大堆）：堆顶是最大元素，越大的优先级越高
Java 中 PriorityQueue 默认是小根堆。
堆 vs 其他方法的选择策略
这是面试中的高频决策点：
| 问题 | 堆 | 其他方法 | 怎么选 |
|---|---|---|---|
| 第 K 大（静态数组） | O(n log k) | 快速选择 O(n) 平均 | 求稳用堆，追求最优用快选 |
| Top K 频率 | O(n log k) | 桶排序 O(n) | k 小时堆好，数据范围确定时桶更好 |
| 数据流中位数 | 只能用堆 | — | 双堆是唯一解 |
| 合并 K 个链表 | O(N log k) | 归并 O(N log k) | 堆更直观，归并空间更优 |
| 滑动窗口最大值 | O(n log n) | 单调队列 O(n) | 堆更易想到，单调队列更优 |
核心特征（什么时候该想到用它）
| 特征 | 说明 |
|---|---|
| ”第 K 大/小” | 小根堆维护前 K 大，大根堆维护前 K 小 |
| ”Top K” | 不需要全排序，只需要前 K 个 |
| 动态中位数 | 双堆：大根堆 + 小根堆 |
| 多路归并 | K 个有序序列，每次取最小 |
| 数据流 | 不断有新数据进来，需要实时知道某统计量 |
识别信号词
- “第 K 个最大/最小”、“前 K 个” → 堆（或快速选择）
- “数据流”、“动态”、“中位数” → 双堆
- “合并 K 个” → 堆多路归并
- “滑动窗口” + “最大值” → 堆（存值和下标，清理过期）
Java PriorityQueue 速查
// 默认小根堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 大根堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// 自定义比较器（例如按频率排序）
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
minHeap.offer(x); // 插入 O(log n)
minHeap.poll(); // 弹出堆顶（最小/最大）O(log n)
minHeap.peek(); // 查看堆顶（不删除）O(1)
minHeap.size(); // 大小
minHeap.remove(x); // 删除指定元素 O(n)——尽量别用二、Hot 100 精讲题目
215. Kth Largest Element in an Array 数组中的第K个最大元素
📌 找数组中第 K 个最大元素（不是排序后第 K 个，而是从大到小第 K 个）。如
[3,2,1,5,6,4], k=2→ 5（最大是 6，第二大是 5）
🔍 解题分析
堆解法思路：维护一个大小为 K 的小根堆。为什么用小根堆？
- 小根堆的堆顶是堆中最小的元素
- 堆中保存的是”到目前为止的前 K 大”元素
- 堆顶就是这些前 K 大中最小的那个 → 即第 K 大
核心思路（步骤化）
- 遍历数组每个元素
- 元素入小根堆
- 如果堆大小 > K，弹出堆顶（把当前 K+1 大中最小的丢掉）
- 遍历完，堆顶就是第 K 大
为什么小根堆存”前 K 大”而不是大根堆：大根堆的堆顶是最大值，如果我们要找第 K 大，需要把所有元素都入堆再弹出 K 次。而小根堆只保留 K 个——因为堆顶是堆中最小的，如果堆里有 K 个元素，堆顶自然就是这些元素里的第 K 大。
堆 vs 快速选择：
| 堆 | 快速选择 | |
|---|---|---|
| 时间 | O(n log k) | O(n) 平均，O(n²) 最坏 |
| 空间 | O(k) | O(log n)（递归栈） |
| 优点 | 稳，支持数据流 | 更快，理论最优 |
| 面试 | 必会 | 加分项 |
✅ 完整 Java 实现
public int findKthLargest(int[] nums, int k) {
// 小根堆：堆顶是堆里最小的，用于维护"前 K 大"
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
// 每个元素先进堆
minHeap.offer(num);
// 堆大小超过 K 时，把最小的弹掉
// 这样堆里始终保留着最大的 K 个
if (minHeap.size() > k) {
minHeap.poll();
}
}
// 堆里是前 K 大，堆顶（最小的）就是第 K 大
return minHeap.peek();
}手算验证：nums = [3, 2, 1, 5, 6, 4], k = 2
| 步骤 | 入堆 | 堆内容 | size > k? | 弹出 | 堆最终 |
|---|---|---|---|---|---|
| 1 | 3 | [3] | ✗ | — | [3] |
| 2 | 2 | [2, 3] | ✗ | — | [2, 3] |
| 3 | 1 | [1, 3, 2] | ✓ | 1 | [2, 3] |
| 4 | 5 | [2, 5, 3] | ✓ | 2 | [3, 5] |
| 5 | 6 | [3, 5, 6] | ✓ | 3 | [5, 6] |
| 6 | 4 | [4, 6, 5] | ✓ | 4 | [5, 6] |
堆顶 = 5 = 第 2 大 ✓
⏱ 复杂度分析
- 时间复杂度：O(n log k) —— n 次操作，每次入堆/出堆 O(log k)
- 空间复杂度：O(k) —— 堆中最多 k 个元素
💡 记忆口诀
“小根堆装前 K 大，超了 K 个弹最小的，堆顶就是第 K 大”
347. Top K Frequent Elements 前 K 个高频元素
📌 找出出现频率前 K 高的元素。如
[1,1,1,2,2,3], k=2→[1,2]
🔍 解题分析
这道题的堆解法和 215 本质一样：维护一个按频率排序的小根堆，保持堆大小为 K。不同之处在于比较器的定义。
核心思路（步骤化）
- HashMap 统计每个元素的出现频率
- 遍历 HashMap 的 keySet，用小根堆维护频率前 K 高的元素
- 堆的比较器：
(a, b) -> freqMap.get(a) - freqMap.get(b)，频率低的在堆顶 - 堆大小超过 K 时弹出频率最低的
- 将堆中元素倒序取出
堆 vs 桶排序：
| 堆（O(n log k)） | 桶排序（O(n)） | |
|---|---|---|
| 优点 | 空间 O(k)，k 小时很快 | 线性时间 |
| 缺点 | log k 开销 | 需要 O(n) 额外空间 |
| 选择 | k << n 时用堆 | 数据量大、k 也大时用桶 |
关键边界条件：比较器写成 freqMap.get(a) - freqMap.get(b) 而不是 b - a，确保是小根堆（频率低的在堆顶优先被弹出）。
✅ 完整 Java 实现
public int[] topKFrequent(int[] nums, int k) {
// 1. 统计每个元素出现的频率
// key = 元素, value = 出现次数
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// 2. 小根堆：按频率从小到大排列
// 堆顶是频率最小的，方便被弹出
PriorityQueue<Integer> minHeap = new PriorityQueue<>(
(a, b) -> freqMap.get(a) - freqMap.get(b) // 按频率升序
);
for (int num : freqMap.keySet()) {
minHeap.offer(num); // 入堆
if (minHeap.size() > k) {
minHeap.poll(); // 弹掉频率最低的
}
}
// 3. 取出结果（从堆中按任意顺序取出即可，或者倒序保证从高到低）
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = minHeap.poll();
}
return result;
}⏱ 复杂度分析
- 时间复杂度：O(n log k) —— n 是 HashMap 不同 key 的数量
- 空间复杂度：O(n) —— HashMap + O(k) 堆
💡 记忆口诀
“频率当权重，小根堆按频率筛；频率低的先弹，留下的就是 Top K”
295. Find Median from Data Stream 数据流的中位数
📌 设计数据结构，支持不断添加整数，并能随时返回当前所有数的中位数。
🔍 解题分析
为什么必须用双堆
数据流意味着数据不停进来，如果每次都用排序求中位数，代价 O(n log n)。双堆可以做到插入 O(log n)，查询 O(1)。
双堆设计
把数据流切成”左半”和”右半”两半：
- 大根堆（leftMaxHeap）：存较小的一半数。堆顶是左半的最大值（离中位数最近的那个小值）
- 小根堆（rightMinHeap）：存较大的一半数。堆顶是右半的最小值（离中位数最近的那个大值）
平衡规则：两个堆大小差 ≤ 1，且让左堆（大根堆）可以多一个。这样：
- 奇数个元素：中位数 = 左堆堆顶
- 偶数个元素：中位数 = (左堆堆顶 + 右堆堆顶) / 2
addNum 操作流程（步骤化）
- 新数先入左堆（大根堆）
- 把左堆的最大值移到右堆（保证右堆的数都比左堆大）
- 如果右堆比左堆大 → 把右堆最小值移回左堆（保证左堆 size ≥ 右堆 size）
这个”先放左边，把最大的给右边，再平衡大小”的三步保证了两个堆的性质始终正确。
类比：想象你面前有两排书架。左边的书都比右边薄（左边是大根堆，最厚的在最右边；右边是小根堆，最薄的在最左边）。新来一本书，先放左边。如果左边最厚的比右边最薄的还厚，就把左边最厚的移到右边。然后调整两边数量相等。
关键边界条件/易错点
| 易错点 | 说明 |
|---|---|
| 初始为空 | 新元素进左堆后，左堆→右堆 再 右堆→左堆，最终左堆多一个 |
| 大根堆的比较器 | (a, b) -> b - a 不能忘记 |
| 中位数用 double | 偶数时要除 2.0，不是 2 |
✅ 完整 Java 实现
class MedianFinder {
// 左半：大根堆，存较小的一半数，堆顶是左半最大值
private PriorityQueue<Integer> leftMaxHeap;
// 右半：小根堆，存较大的一半数，堆顶是右半最小值
private PriorityQueue<Integer> rightMinHeap;
public MedianFinder() {
// 大根堆：传入比较器反转顺序
leftMaxHeap = new PriorityQueue<>((a, b) -> b - a);
// 小根堆：默认就是小根堆
rightMinHeap = new PriorityQueue<>();
}
public void addNum(int num) {
// 步骤1：新元素先放入左半（大根堆）
leftMaxHeap.offer(num);
// 步骤2：把左半的最大值移到右半
// 这保证了右半的所有数都 ≥ 左半的所有数
rightMinHeap.offer(leftMaxHeap.poll());
// 步骤3：平衡两个堆的大小
// 保持 leftMaxHeap.size() >= rightMinHeap.size()
// 且两者差距不超过 1
if (leftMaxHeap.size() < rightMinHeap.size()) {
leftMaxHeap.offer(rightMinHeap.poll());
}
}
public double findMedian() {
// 奇数个元素：左堆比右堆多一个，中位数在左堆堆顶
if (leftMaxHeap.size() > rightMinHeap.size()) {
return leftMaxHeap.peek();
}
// 偶数个元素：中位数 = (左堆堆顶 + 右堆堆顶) / 2
return (leftMaxHeap.peek() + rightMinHeap.peek()) / 2.0;
}
}手算验证：依次插入 [3, 1, 5, 2]
| 步骤 | 操作 | 左堆 (大根) | 右堆 (小根) | 中位数 |
|---|---|---|---|---|
| add(3) | 3入左, 左→右, 右<左不调 | [3] | [] | 3.0 |
| add(1) | 1入左→[3,1], 左→右(3), 左=[1],右=[3] | [1] | [3] | (1+3)/2=2.0 |
| add(5) | 5入左→[5,1], 左→右(5), 左=[1],右=[5,3], 右>左→调, 左=[3,1],右=[5] | [3,1] | [5] | 3.0 |
| add(2) | 2入左→[3,1,2], 左→右(3), 左=[2,1],右=[3,5] | [2,1] | [3,5] | (2+3)/2=2.5 |
⏱ 复杂度分析
- 时间复杂度：addNum O(log n) —— 最多 3 次堆操作；findMedian O(1) —— 只看堆顶
- 空间复杂度：O(n) —— 存储所有元素
💡 记忆口诀
“大根堆管左半（小的那边），小根堆管右半（大的那边）；新数先入左，把最大的给右，再平衡左右；中位数在两个堆顶之间”
239. Sliding Window Maximum 滑动窗口最大值（堆解法）
📌 详见 03-滑动窗口。此题最优解是单调队列 O(n)，但堆解法更直观。
🔍 解题分析
堆解法核心：大根堆同时存 (值, 下标)，按值降序。每次窗口移动后：
- 新元素入堆
- 检查堆顶是否还在窗口内（下标 > i - k 说明还在）
- 不在就弹出，直到堆顶在窗口内
- 堆顶就是当前窗口的最大值
堆 vs 单调队列：
| 堆 | 单调队列 | |
|---|---|---|
| 时间 | O(n log n) | O(n) |
| 空间 | O(n) | O(k) |
| 思路 | 自然直观 | 需要理解单调性 |
| 面试 | 优先想到 | 更优解，加分项 |
为什么堆中有过期元素也没问题：我们只在需要答案时才清理堆顶。这叫做”懒删除”——不是每个过期元素都立即删，而是只删那些挡在堆顶的过期元素。
✅ 完整 Java 实现
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
// 大根堆：int[]{值, 下标}，按值降序排列
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
(a, b) -> b[0] - a[0] // b[0]-a[0] > 0 则 b 在前，即值大的在前
);
for (int i = 0; i < n; i++) {
// 新元素入堆
maxHeap.offer(new int[]{nums[i], i});
// 窗口形成（前 k 个已入堆）后开始记录答案
if (i >= k - 1) {
// 懒删除：清理堆顶中已经滑出窗口的元素
// 窗口范围是 [i-k+1, i]，下标 ≤ i-k 的都是过期的
while (maxHeap.peek()[1] <= i - k) {
maxHeap.poll();
}
// 清理后的堆顶就是当前窗口最大值
result[i - k + 1] = maxHeap.peek()[0];
}
}
return result;
}⏱ 复杂度分析
- 时间复杂度：O(n log n) —— n 次入堆/出堆操作，每次 O(log n)
- 空间复杂度：O(n) —— 堆中可能堆积很多过期元素
💡 记忆口诀
“大根堆存 (值, 下标)，每次查答案前先弹走过期的老大”
23. Merge k Sorted Lists 合并 K 个升序链表（堆解法）
📌 详见 08-链表。堆解法比归并更直观。
🔍 解题分析
堆多路归并：把所有链表的头节点放入小根堆（按节点值排序）。每次弹出最小的节点，接到结果链表尾部。如果弹出的节点有后继，把后继也入堆。重复直到堆空。
为什么堆更适合：K 路归并的核心操作是”每次找 K 个中的最小值”。堆正好擅长”动态维护一组元素的最小值”。
堆 vs 归并：
| 堆 | 归并（分治） | |
|---|---|---|
| 实现难度 | 直观，代码短 | 需要注意分治边界 |
| 时间复杂度 | O(N log k) | O(N log k) |
| 空间复杂度 | O(k)（堆） | O(log k)（递归栈） |
| 适合场景 | K 很大时 | K 较小时 |
关键细节：遍历 lists 数组时，空链表（head==null）要跳过，不入堆。pop 最小节点后，如果它的 next 不为 null，要把 next 也入堆——这是不同于普通堆操作的地方。
✅ 完整 Java 实现
public ListNode mergeKLists(ListNode[] lists) {
// 小根堆：按节点值升序，堆顶是最小的节点
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
(a, b) -> a.val - b.val
);
// 将每个非空链表的头节点入堆
for (ListNode head : lists) {
if (head != null) {
minHeap.offer(head);
}
}
// 哨兵节点，统一插入逻辑
ListNode dummy = new ListNode(0);
ListNode cur = dummy; // cur 始终指向结果链表的最后一个节点
while (!minHeap.isEmpty()) {
// 弹出当前最小的节点
ListNode minNode = minHeap.poll();
cur.next = minNode;
cur = cur.next;
// 【关键】如果弹出的节点有后继，把后继入堆
// 这样每条链表的下一个候选节点始终在堆中
if (minNode.next != null) {
minHeap.offer(minNode.next);
}
}
return dummy.next;
}⏱ 复杂度分析
- 时间复杂度：O(N log k) —— N 是总节点数，每个节点入堆出堆各一次，每次 O(log k)
- 空间复杂度：O(k) —— 堆中最多同时存放 k 个节点
💡 记忆口诀
“所有头节点入小根堆，每次弹最小接上去，有后继继续入堆”