堆与优先队列
堆是面试中非常重要的高频考点。关键不是背代码，而是理解堆为什么能高效地找到最大/最小值，以及什么时候该用堆。
面试考察点
面试官通过这道题想考察：
1. 你是否理解堆作为完全二叉树的性质
2. 你是否能解释为什么堆的插入删除是 O(log n)
3. 你是否理解 Top K 问题的最优解
4. 你是否能区分堆和其他数据结构的应用场景
一、什么是堆？
1.1 堆的直观理解
面试官追问："什么是堆？为什么叫堆？"
堆（Heap） = 一棵完全二叉树 + 堆属性
完全二叉树：除了最后一层，其他层都是满的，最后一层从左到右排列
堆属性：
- 最大堆：父节点 >= 子节点
- 最小堆：父节点 <= 子节点
示例（最大堆）：
9
/ \
7 8
/ \ / \
5 6 4 7
/
1
验证：
- 每个父节点都比子节点大 ✓
- 是一棵完全二叉树 ✓
特点：
根节点是最大值（最大堆）或最小值（最小堆）！
找最大/最小值只需要 O(1)！
1.2 为什么用数组存储堆？（面试必问）
面试官追问："堆为什么用数组存储而不是链表？"
完全二叉树的特点：可以用数组高效存储！
9(0)
/ \
7(1) 8(2)
/ \ / \
5(3)6(4) 4(5)7(6)
/
1(7)
数组表示：
索引： 0 1 2 3 4 5 6 7
值： [9, 7, 8, 5, 6, 4, 7, 1]
↑ ↑
根节点 最后一个节点
父子关系公式（i 是节点索引）：
- 父节点索引 = (i - 1) / 2
- 左子节点索引 = 2 * i + 1
- 右子节点索引 = 2 * i + 2
为什么不用链表？
因为堆是完全二叉树，结构固定，用数组更节省空间（不需要存指针）
而且访问父子节点只需要 O(1) 的数学计算！
1.3 堆的"冒泡"操作（核心原理）
面试官追问："堆的插入和删除为什么是 O(log n)？"
堆的插入（上浮 / bubble up）：
1. 把新元素放到数组最后
2. 如果它比父节点大（最大堆），就和父节点交换
3. 重复，直到满足堆属性
图解：
初始最大堆： 插入 10：
9 9
/ \ / \
7 8 → 7 8
/ \ / \
5 6 5 6
/
10 ← 新节点
10 比父节点 8 大，交换：
9 9
/ \ / \
7 10 → 7 10
/ \ / / / \
5 6 8 5 6 8
/
10
10 比父节点 9 大，交换：
10 10
/ \ / \
7 9 → 7 9
/ \ / \ / \ \
5 6 8 1 5 6 8
/
1
完成！
复杂度分析：
- 完全二叉树高度 = log₂(n)
- 最多交换 log₂(n) 次
- 所以是 O(log n)！
堆的删除（下沉 / bubble down）：
删除堆顶（比如根节点），然后重新调整堆：
1. 把最后一个元素移到堆顶
2. 如果它比子节点小（最大堆），就和较大的子节点交换
3. 重复，直到满足堆属性
复杂度同样是 O(log n)！
二、优先队列
2.1 什么是优先队列？（和普通队列的区别）
普通队列：FIFO，先来先服务
优先队列：优先级高的先服务
应用场景：
- 医院急诊：重症患者优先
- 任务调度：优先级高的任务先执行
- Top K 问题：找最大的 K 个元素
2.2 堆就是优先队列的实现！（面试核心）
面试官追问："优先队列怎么实现？为什么用堆？"
优先队列用堆实现！
为什么用堆？
- 找到最大/最小值：O(1)
- 插入：O(log n)
- 删除最大/最小：O(log n)
对比其他数据结构：
| 数据结构 | 插入 | 取最大/最小 | 总复杂度 |
|--------------|---------|------------|--------------|
| 无序数组 | O(1) | O(n) | O(n) 取最大 |
| 有序数组 | O(n) | O(1) | O(n) 插入 |
| 平衡二叉搜索树 | O(log n)| O(1)或O(log n)| O(log n) |
| 堆 | O(log n)| O(1) | O(log n) ✓ |
堆是最优选择：插入和删除都是 O(log n)，且实现简单！
三、Top K 问题（面试高频）
3.1 Top K 问题的最优解
面试官追问："怎么找第 K 大的元素？Top K 用什么方法？"
问题：找第 K 大的元素（或最大的 K 个元素）
方法比较：
方法1：排序
- 对数组排序，取第 K 个
- 时间：O(n log n)
- 空间：O(1)
方法2：堆排序思想
- 维护一个大小为 K 的最小堆
- 遍历数组，把元素加入堆
- 如果堆大小 > K，弹出堆顶（最小的）
- 最后堆顶就是第 K 大的元素
- 时间：O(n log K)
- 空间：O(K)
面试回答：通常用方法2，因为：
1. n 可能很大，log n 可能很大
2. K 通常远小于 n，log K << log n
3. 如果 n=10^9，K=10，显然 O(n log K) 比 O(n log n) 快得多
3.2 堆排序（理解原理）
面试官追问："堆排序怎么实现？"
堆排序 = 建堆 + 逐个取出最大
步骤：
1. 把数组建成最大堆
2. 交换堆顶和堆尾
3. 把前面的 n-1 个元素重新调整为堆
4. 重复 2-3
为什么叫"原地排序"？
因为只需要 O(1) 的额外空间！
复杂度分析：
- 建堆：O(n)
- 排序：n-1 次，每次 O(log n)
- 总复杂度：O(n log n)
对比快速排序：
- 两者都是 O(n log n)
- 快速排序的常量更小（实际更快）
- 堆排序是原地排序（空间更少）
四、面试总结
堆的核心特点
┌─────────────────────────────────────────────────┐
│ 堆 │
├─────────────────────────────────────────────────┤
│ │
│ 结构：完全二叉树，用数组存储 │
│ │
│ 性质： │
│ - 最大堆：根是最大值 │
│ - 最小堆：根是最小值 │
│ │
│ 操作复杂度： │
│ - 找最大/最小值：O(1) │
│ - 插入：O(log n) │
│ - 删除最大/最小：O(log n) │
│ │
│ 应用： │
│ - 优先队列 │
│ - Top K 问题 │
│ - 中位数问题 │
│ │
└─────────────────────────────────────────────────┘
面试能加分的回答
1. 能解释为什么用数组存堆
"完全二叉树的父子关系可以用数学公式计算，
不需要指针，节省空间"
2. 能解释为什么是 O(log n)
"完全二叉树高度是 log n，
插入/删除最多交换 log n 次"
3. 能解释 Top K 的最优解
"维护大小为 K 的堆，时间 O(n log K)"
4. 能说出堆的应用场景
"优先队列、Top K、中位数、合并 K 个有序数组"
相关题目
- LeetCode 215 - 数组中的第K个最大元素 - Top K
- LeetCode 295 - 数据流的中位数 - 堆应用
- LeetCode 23 - 合并K个升序链表 - 堆应用