Appearance
堆与优先队列
概念
堆（Heap）是满足堆序性的完全二叉树，通常用数组顺序存储：
- 大根堆（最大堆）：任一结点的值 ≥ 其左右孩子的值，即
- 小根堆（最小堆）：任一结点的值 ≤ 其左右孩子的值。
优先队列（Priority Queue）是只关心"最大/最小那个元素"的队列：出队时总是弹出优先级最高者。堆是优先队列的标准实现——堆顶就是最值，取最值 O(1)。
一句话理解：堆是"只保证父子有序、不保证兄弟有序"的完全二叉树，代价极小地换来了 O(1) 取最值 + O(log n) 插入删除。
原理
顺序存储的编号关系
因为是完全二叉树，可以紧凑地放进数组而不留空洞。设数组从下标 1 开始存放（a[0] 空置，这是 408 教材的惯例）：
| 关系 | 从 1 开始编号 | 从 0 开始编号 |
|---|---|---|
| i 的双亲 | ||
| i 的左孩子 | ||
| i 的右孩子 | ||
| 是叶子的条件 | ||
| n 个结点的高度 | 同左 |
本文正文与代码统一用从 1 开始的编号。若你习惯 C 数组从 0 开始，把上表右列套上即可，逻辑完全一致。
两个基本动作
| 动作 | 别名 | 方向 | 用途 |
|---|---|---|---|
| 向下调整 | 筛选、Sift Down、Heapify | 从上往下 | 删除堆顶、建堆 |
| 向上调整 | 上滤、Sift Up | 从下往上 | 插入新元素 |
向下调整（以大根堆为例）：把结点 i 视为" vacancy（空位）"，在它的左右孩子中挑更大的那个，若比待调整元素大，就把它上移到空位，空位随之下移一层；重复直到空位落到叶子或孩子都不比它大，最后把元素放入空位。
向上调整：新元素放在末尾，若比双亲大就与双亲交换，一路向上直到不比双亲大或到达根。
两者都只走一条路径，路径长不超过树高，故均为 O(log n)。
建堆：自底向下，O(n)
从最后一个非叶结点
为什么必须从下往上？因为向下调整要求"子树已经是堆"，自底向上保证了处理 i 时它的左右子树都已成堆。
为什么是 O(n) 而不是 O(n log n)：大部分结点靠近底层，它们下滤的距离很短。第 k 层（根为第 1 层）至多
所以建堆是 O(n)。反过来，逐个插入建堆是 O(n log n)——两者别混淆。
四个操作的复杂度
| 操作 | 做法 | 复杂度 |
|---|---|---|
| 建堆 | 自底向上对每个非叶下滤 | O(n) |
| 取最值 | 直接读 a[1] | O(1) |
| 插入 | 放末尾 + 上滤 | O(log n) |
| 删除堆顶 | 用末尾元素顶替 a[1] + 下滤 | O(log n) |
堆排序
思路（升序排序用大根堆）：
- 把待排序列建成大根堆（a[1] 是最大值）；
- 重复 n−1 次：把 a[1] 与当前堆的最后一个元素交换（最大值归位到末尾），堆长度减 1，再对 a[1] 下滤。
| 性质 | 结论 |
|---|---|
| 时间复杂度 | 建堆 O(n) + (n−1) 次下滤 O(n log n) = O(n log n)，最好/最坏/平均都是 O(n log n) |
| 空间复杂度 | O(1)（原地） |
| 稳定性 | 不稳定（如 3, 3，后面的 3 可能先归位） |
| 排序方向 | 大根堆 → 升序；小根堆 → 降序 |
| 比较次数 | 与序列初始状态有关，但不超过 |
对比：快排平均更快但最坏 O(n²) 且递归需栈；堆排序胜在最坏也是 O(n log n) 且空间 O(1)，败在不稳定、常数大、对 Cache 不友好（跳着访问数组）。
堆 ≠ 二叉排序树
| 堆 | 二叉排序树 | |
|---|---|---|
| 有序性 | 只保证父子有序 | 保证左 < 根 < 右 |
| 能否中序有序输出 | 不能 | 能（中序即升序） |
| 查某个值 | O(n) | O(log n) |
| 取最值 | O(1) | O(log n) |
| 形态 | 必须是完全二叉树 | 任意 |
示例
例：建大根堆 + 堆排序
对关键字序列
53, 17, 78, 9, 45, 65, 87, 23建大根堆，写出每步结果，并给出堆排序的前两趟与最终序列。
完整推导过程：
初始（a[1..8]）：53, 17, 78, 9, 45, 65, 87, 23
对应的完全二叉树：
53
/ \
17 78
/ \ / \
9 45 65 87
/
23n = 8，最后一个非叶结点 = ⌊8/2⌋ = 4，从 i = 4 向前处理。
第一步，i = 4（值 9），左孩子 a[8] = 23 > 9 → 上移：
53, 17, 78, 23, 45, 65, 87, 9第二步，i = 3（值 78），孩子 a[6] = 65、a[7] = 87，较大者 87 > 78 → 上移：
53, 17, 87, 23, 45, 65, 78, 9第三步，i = 2（值 17），孩子 a[4] = 23、a[5] = 45，较大者 45 > 17 → 上移：
53, 45, 87, 23, 17, 65, 78, 9第四步，i = 1（值 53），孩子 a[2] = 45、a[3] = 87，较大者 87 > 53 → 上移；空位落到 3，其孩子 a[6] = 65、a[7] = 78，较大者 78 > 53 → 继续上移；空位落到 7（叶子），53 放入：
87, 45, 78, 23, 17, 65, 53, 9大根堆建成：
87
/ \
45 78
/ \ / \
23 17 65 53
/
9第五步，堆排序第一趟：把 a[1] = 87 与 a[8] = 9 交换 → 87 归位；堆长减为 7，对 a[1] 下滤（9 与孩子 45、78 中较大的 78 交换，再与 65 交换）：
交换后：9, 45, 78, 23, 17, 65, 53 | 87
下滤后：78, 45, 65, 23, 17, 9, 53 | 87第六步，第二趟：78 与 a[7] = 53 交换 → 78 归位；堆长减为 6，下滤：
交换后：53, 45, 65, 23, 17, 9 | 78, 87
下滤后：65, 45, 53, 23, 17, 9 | 78, 87第七步，重复到第 7 趟结束，最终升序序列：
9, 17, 23, 45, 53, 65, 78, 87C 语言：大根堆与堆排序（下标从 1 开始）
#include <stdio.h>
/* 向下调整：在 a[low..high] 中，以 a[low] 为待调整元素做下滤（大根堆） */
void siftDown(int a[], int low, int high) {
int i = low, j = 2 * i; /* j 指向 i 的左孩子 */
int tmp = a[i]; /* 先挖出来，形成"空位" */
while (j <= high) {
if (j + 1 <= high && a[j + 1] > a[j]) j++; /* 取更大的孩子 */
if (a[j] <= tmp) break; /* 孩子都不比我大，到位 */
a[i] = a[j]; /* 孩子上移 */
i = j; j = 2 * i; /* 空位下移一层 */
}
a[i] = tmp; /* 元素落位 */
}
/* 向上调整：插入末尾元素后上滤 */
void siftUp(int a[], int i) {
int tmp = a[i];
while (i > 1 && tmp > a[i / 2]) {
a[i] = a[i / 2];
i /= 2;
}
a[i] = tmp;
}
/* 建大根堆：自底向上对每个非叶结点下滤 */
void buildMaxHeap(int a[], int n) {
for (int i = n / 2; i >= 1; i--) siftDown(a, i, n);
}
/* 堆排序：大根堆 -> 升序 */
void heapSort(int a[], int n) {
buildMaxHeap(a, n);
for (int i = n; i > 1; i--) {
int t = a[1]; a[1] = a[i]; a[i] = t; /* 堆顶（最大）归位到末尾 */
siftDown(a, 1, i - 1);
}
}
/* 优先队列：删除堆顶 */
int popMax(int a[], int *n) {
int top = a[1];
a[1] = a[*n];
(*n)--;
siftDown(a, 1, *n);
return top;
}
int main(void) {
int a[9] = {0, 53, 17, 78, 9, 45, 65, 87, 23}; /* a[0] 空置 */
int n = 8;
buildMaxHeap(a, n);
printf("大根堆: ");
for (int i = 1; i <= n; i++) printf("%d ", a[i]); /* 87 45 78 23 17 65 53 9 */
printf("\n");
printf("弹出堆顶: %d, %d\n", popMax(a, &n), popMax(a, &n)); /* 87 78 */
int b[9] = {0, 53, 17, 78, 9, 45, 65, 87, 23};
heapSort(b, 8);
printf("堆排序: ");
for (int i = 1; i <= 8; i++) printf("%d ", b[i]); /* 9 17 23 45 53 65 78 87 */
printf("\n");
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
def sift_down(a, low, high):
"""a 为 1-indexed 列表（a[0] 占位）"""
i, j, tmp = low, 2 * low, a[low]
while j <= high:
if j + 1 <= high and a[j + 1] > a[j]:
j += 1
if a[j] <= tmp:
break
a[i] = a[j]
i, j = j, 2 * j
a[i] = tmp
def build_max_heap(a, n):
for i in range(n // 2, 0, -1):
sift_down(a, i, n)
def heap_sort(a, n):
build_max_heap(a, n)
for i in range(n, 1, -1):
a[1], a[i] = a[i], a[1]
sift_down(a, 1, i - 1)
a = [0, 53, 17, 78, 9, 45, 65, 87, 23]
n = 8
build_max_heap(a, n)
print("大根堆:", a[1:]) # [87, 45, 78, 23, 17, 65, 53, 9]
b = [0, 53, 17, 78, 9, 45, 65, 87, 23]
heap_sort(b, 8)
print("堆排序:", b[1:]) # [9, 17, 23, 45, 53, 65, 78, 87]
# 用 Python 标准库（小根堆）实现优先队列：取 Top-k
import heapq
nums = [53, 17, 78, 9, 45, 65, 87, 23]
print("最小的 3 个:", heapq.nsmallest(3, nums)) # [9, 17, 23]
print("最大的 3 个:", heapq.nlargest(3, nums)) # [87, 78, 65]
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- 堆是完全二叉树，只保证父子有序，兄弟之间无序，中序遍历不是有序序列（这是与二叉排序树的分水岭）。
- 最后一个非叶结点下标 =
- 建堆 O(n)（自底向上），逐个插入建堆 O(n log n)。
- 插入 = 末尾 + 上滤；删除堆顶 = 末尾顶替 + 下滤；都是 O(log n)；取最值 O(1)。
- 堆排序：O(n log n)、O(1) 空间、不稳定；大根堆得升序，小根堆得降序。
- n 个元素建堆后，堆顶一定是最大（小）值，但整个数组不是有序的。
2. 解题套路
- 手算建堆：先画完全二叉树 → 从
⌊n/2⌋往前逐个下滤 → 每步只在一条路径上动。 - 手算堆排序：每趟"交换堆顶与末尾 → 堆长减 1 → 下滤"，写三行就够，别试图在图上操作。
- 题目问"第 k 趟排序后的序列"：前 k 个最大值已经归位到尾部，头部是剩余部分的堆。
3. 易错点
- 排序方向反了：大根堆每次把最大送到末尾，得到的是升序。记法："大根堆 = 每次冒一个最大的到后面 = 升序"。
- 认为堆排序是稳定的。反例：序列
3a, 3b，建堆后 3a 在根、3b 在下层，第一趟 3a 被换到末尾，3b 反而排在前面 → 不稳定。 - 把"建堆"复杂度记成 O(n log n)。关键是底层结点多但下滤距离短，求和后是 O(n)。
- 编号从 0 还是从 1 开始：题目给的数组若从 0 开始，左孩子是
2i+1而不是2i。先在草稿上固定一种，全程不改。 - 向下调整的循环里，"空位"是先只移孩子、最后才放 tmp 的写法；若写成一路
swap交换也能得到正确结果，但比较/移动次数更多，且两种写法产生的堆可能不同（都合法）。 - 堆适合取最值，不适合查找任意关键字（O(n)）。题目说"查找第 k 小"别急着用堆，那是选择问题。
小结
- 堆 = 完全二叉树 + 堆序性，用数组紧凑存储；父子有序、兄弟无序。
- 两个基本动作：向下调整（删除、建堆）、向上调整（插入），均 O(log n)。
- 自底向上建堆是 O(n)，这是最容易被记错、也最爱考的结论。
- 堆排序：O(n log n)、O(1) 空间、不稳定，大根堆出升序。
- 下一步：从线性与树形结构进入最一般的结构——图。
下一篇：图：邻接矩阵与邻接表
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。