Appearance
堆
为什么把"堆"单独拎出来讲
很多同学第一次见到"堆"是在堆排序里，于是默认堆只是排序的副产品。这是 408 的一个理解误区——堆是一种独立的数据结构，堆排序只是它的一个应用，其它应用包括优先队列、TopK 问题、哈夫曼树的合并过程等。
408 真题里直接考"堆操作"的频次也不低：给一个数组问是不是堆、给序列让你画建堆过程、对一个堆做插入或删除后画出形态——这些都不是"排序题"，而是"数据结构题"。
核心思想
堆（Heap）是一棵满足堆序性的完全二叉树。所谓堆序性，指的是：
- 大根堆（Max Heap）：每个结点的值都大于等于其孩子的值
- 小根堆（Min Heap）：每个结点的值都小于等于其孩子的值
注意三点：
- 堆不是有序的——堆只保证"双亲优于孩子"，不保证左右孩子之间或同一层之间有序
- 堆是完全二叉树——这是它能用数组顺序存储的根本原因
- 根永远是最值——大根堆的根是最大值、小根堆的根是最小值，这是 O(1) 取最值的来源
大根堆 小根堆
9 1
/ \ / \
7 8 3 2
/ \ / \ / \ / \
4 6 5 3 7 4 8 6观察大根堆：每个三角（双亲 + 两孩子）内，双亲都最大；但 7 < 8、4 < 6 这种"同层比较"或"跨子树比较"是不要求的。
交互可视化
下方动画演示数组建堆 + 堆排序的完整过程，可以观察每次下沉调整时的元素交换路径：
操作详解
一、堆的存储——为什么必须是数组
堆是完全二叉树，所以可以用数组按层序编号顺序存储，无需指针。给定结点下标 i，双亲和孩子的下标可以直接算出来：
下标从 1 开始（A[1..n]，408 主流约定，下面所有代码均按此）：
| 关系 | 公式 |
|---|---|
| 双亲 parent(i) | ⌊i / 2⌋ |
| 左孩子 left(i) | 2i |
| 右孩子 right(i) | 2i + 1 |
| 最后一个非叶结点 | ⌊n / 2⌋ |
| 叶子结点范围 | ⌊n/2⌋ + 1 ~ n |
下标从 0 开始（A[0..n-1]，工业语言通常约定）：
| 关系 | 公式 |
|---|---|
| 双亲 parent(i) | ⌊(i - 1) / 2⌋ |
| 左孩子 left(i) | 2i + 1 |
| 右孩子 right(i) | 2i + 2 |
| 最后一个非叶结点 | ⌊n / 2⌋ - 1 |
⚠️ 易错：408 真题下标多数从 1 开始，但部分题目（特别是程序填空）会切换到 0。第一步永远先看清题目约定，否则双亲孩子算错一格。
二、下沉调整（Sift Down / 向下调整）
下沉是堆操作的最核心动作。场景是：某个结点 i 不满足堆序性（值比孩子小，以大根堆为例），需要把它"沉"下去。
算法：
- 比较 i 与它的左右孩子，找到最大的那个（设下标为
largest） - 如果
largest == i，已经满足堆序，结束 - 否则交换
A[i]与A[largest]，然后对largest位置递归下沉
c
// 大根堆下沉调整：从下标 i 开始，堆大小为 n（A[1..n]）
void SiftDown(int A[], int i, int n) {
int temp = A[i]; // 暂存当前结点，避免每次都交换
for (int k = 2 * i; k <= n; k *= 2) {
// 选左右孩子中较大的
if (k < n && A[k] < A[k + 1]) {
k++;
}
if (temp >= A[k]) { // 已满足堆序，停止下沉
break;
}
A[i] = A[k]; // 较大孩子上移
i = k; // i 跟着沉下来
}
A[i] = temp; // 最终位置写入
}复杂度：O(log n)，下沉路径最长 = 树的高度。
优化点：这里用
temp暂存 + 单赋值取代三次赋值的"完整交换"，避免重复写入。408 应试代码可以写成标准 swap，但课本上的"调整"伪代码经常采用这种"单边搬移"写法，识图能看懂即可。
三、上浮调整（Sift Up / 向上调整）
上浮是下沉的逆操作。场景：某个结点的值比双亲大（大根堆），需要"浮"上去。典型用在堆插入：新元素先放到数组末尾，然后从末尾向上调整。
c
// 大根堆上浮调整：从下标 i 向根方向调整
void SiftUp(int A[], int i) {
int temp = A[i];
while (i > 1 && temp > A[i / 2]) {
A[i] = A[i / 2]; // 双亲下移
i = i / 2;
}
A[i] = temp;
}复杂度：O(log n)。
四、建堆（Heapify）——为什么是 O(n)
把一个无序数组变成堆，有两种思路：
思路 A：自顶向下插入（O(n log n)）
把数组看作"逐个插入"的过程，对每个新元素做上浮。每次插入 O(log n)，n 个元素总 O(n log n)。
思路 B：自底向上下沉（O(n)）
直接把数组看成完全二叉树。从最后一个非叶结点 i = n/2 开始，依次往前对每个非叶结点做下沉调整：
c
// 大根堆建堆：O(n)
void BuildMaxHeap(int A[], int n) {
for (int i = n / 2; i >= 1; i--) {
SiftDown(A, i, n);
}
}为什么思路 B 是 O(n) 而不是 O(n log n)：
虽然每次 SiftDown 最坏是 O(log n)，但绝大多数结点的下沉路径都很短。设树高为 h，则：
- 第 h 层（叶子，约 n/2 个）：高度 0，根本不下沉
- 第 h-1 层（约 n/4 个）：下沉最多 1 层
- 第 h-2 层（约 n/8 个）：下沉最多 2 层
- ...
- 根（1 个）：下沉最多 h 层
总代价
直觉记忆：思路 B 高效是因为"大部分结点是叶子，叶子不用下沉"。而思路 A 把每个新结点都假定要爬到根，所以慢。
手算示例：用思路 B 对 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] 建大根堆（下标从 1 开始）。
初始（线性看）：A = [_, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
对应完全二叉树：
4(1)
/ \
1(2) 3(3)
/ \ / \
2(4) 16(5) 9(6) 10(7)
/ \ /
14(8) 8(9) 7(10)
n = 10，最后一个非叶结点 i = n/2 = 5。
i = 5（值 16）: 孩子是 7（下标 10），16 > 7，不下沉。
i = 4（值 2）: 孩子是 14（下标 8）和 8（下标 9），最大是 14。
2 < 14，交换。A[4] = 14, A[8] = 2。
i = 3（值 3）: 孩子是 9（下标 6）和 10（下标 7），最大是 10。
3 < 10，交换。A[3] = 10, A[7] = 3。
i = 2（值 1）: 孩子是 14（下标 4）和 16（下标 5），最大是 16。
1 < 16，交换。A[2] = 16, A[5] = 1。
继续下沉 i = 5，孩子只有 A[10] = 7，1 < 7，交换。
A[5] = 7, A[10] = 1。
i = 1（值 4）: 孩子是 16（下标 2）和 10（下标 3），最大是 16。
4 < 16，交换。A[1] = 16, A[2] = 4。
继续下沉 i = 2，孩子是 14 和 7，最大是 14。
4 < 14，交换。A[2] = 14, A[4] = 4。
继续下沉 i = 4，孩子是 2 和 8，最大是 8。
4 < 8，交换。A[4] = 8, A[9] = 4。
最终大根堆 A = [_, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1]五、堆的插入
算法：把新元素 x 放到数组末尾（即完全二叉树的最后一个位置），然后对它做 SiftUp。
c
void HeapInsert(int A[], int *n, int x) {
(*n)++;
A[*n] = x;
SiftUp(A, *n);
}复杂度：O(log n)。
手算示例：在大根堆 [_, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1] 中插入 15。
末尾追加：A = [_, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1, 15]，n = 11
15 在下标 11，双亲下标 = ⌊11/2⌋ = 5，A[5] = 7。15 > 7，交换：
A = [_, 16, 14, 10, 8, 15, 9, 3, 2, 4, 1, 7]
15 在下标 5，双亲下标 = 2，A[2] = 14。15 > 14，交换：
A = [_, 16, 15, 10, 8, 14, 9, 3, 2, 4, 1, 7]
15 在下标 2，双亲下标 = 1，A[1] = 16。15 < 16，停止。
最终：A = [_, 16, 15, 10, 8, 14, 9, 3, 2, 4, 1, 7]六、堆的删除（删除堆顶）
堆的常规删除指的是删除堆顶元素（即最值），这是优先队列出队的语义。
算法：
- 取出堆顶
A[1]（这就是要返回的值） - 把最后一个元素
A[n]搬到堆顶位置 - 数组大小减 1（
n--） - 对新堆顶做 SiftDown
c
int HeapDeleteTop(int A[], int *n) {
int top = A[1];
A[1] = A[*n];
(*n)--;
SiftDown(A, 1, *n);
return top;
}复杂度：O(log n)。
为什么不是直接"删根然后两个子堆合并"：那样会破坏完全二叉树的形态（最后一层不再连续）。把末尾元素提上来再下沉是保证形态的最简洁方案。
七、堆作为优先队列
优先队列（Priority Queue）是一个 ADT，要求支持：
Insert(x)：插入一个带优先级的元素ExtractTop()：取出并删除优先级最高的元素
用大根堆实现优先队列，两个操作都是 O(log n)。这就是它在系统底层（操作系统进程调度、Dijkstra/Prim 等图算法、哈夫曼合并）被广泛使用的原因。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 建堆（自底向上下沉） | O(n) | O(1)（原地） |
| 建堆（自顶向下插入） | O(n log n) | O(1) |
| 插入一个元素 | O(log n) | O(1) |
| 删除堆顶 | O(log n) | O(1) |
| 查找最大/最小（堆顶） | O(1) | O(1) |
| 查找任意元素 | O(n) | O(1) |
易错：在堆中"查找任意元素"是 O(n)——堆只保证根是最值，不保证任何其它的有序性。如果题目问"在大根堆中查找第 k 大的元素效率"，O(1) 仅对 k = 1 成立。
考研高频考点
- ⭐ 建堆过程的画图题——给定数组用自底向上方法建堆，要求画出每一步的形态（应用题/选择题双高频）
- ⭐ 堆插入后的形态——给一个堆和一个新值，问插入后的结果
- ⭐ 堆删除（删除堆顶）后的形态——给一个堆，问出队一次后的结果
- ⭐ 判定是否是堆——给一个数组（或一个完全二叉树），问是否为大/小根堆
- ⭐ 顺序存储下标关系——双亲、孩子的下标公式（选择题/填空题高频，区分 0-base 和 1-base）
- 建堆 O(n) 的推导（综合题、概念辨析）
- 堆 vs 二叉排序树：堆只保证双亲优于孩子，BST 保证整棵树有序（易错点）
- 优先队列的应用场景（Dijkstra、Prim、哈夫曼合并）
易错：很多同学把"堆"和"堆排序"混在一起。请记住：建堆是 O(n)，堆排序是 O(n log n)——堆排序的总复杂度是"O(n) 建堆 + n 次 O(log n) 删除"= O(n log n)，建堆本身并不慢。
易错：堆的形态不是唯一的——同一组数据可以建出多个合法的大根堆（只要满足堆序，左右孩子顺序无所谓）。但用"自底向上下沉"算法建出来的堆是确定的，画图题以这个为标准答案。
相关知识
- 堆排序：堆作为排序算法的直接应用，建堆 + 反复删除堆顶
- 树与二叉树基本概念：堆基于完全二叉树，复习完全二叉树的性质对理解堆的下标关系很有帮助
- 哈夫曼树：哈夫曼树的构建过程本质上是用最小堆（优先队列）反复合并最小的两棵子树
- Dijkstra 算法、Prim 算法：标准实现都依赖堆来加速"取最小未确定结点"