Appearance
堆排序
O(1) 额外空间的 O(n log n) 排序
堆排序只用 O(1) 额外空间就能保证最坏 O(n log n)——这是快排做不到的。代价是它对 cache 不友好：父子结点在数组中跳跃访问，实际速度常常输给快排的顺序扫描。
408 考研中，堆排序是排序章节的高频考点，尤其是建堆复杂度、稳定性判断以及与快排/归并的横向对比。
核心思想
堆排序分为两个阶段：
- 建堆：将无序数组自底向上调整为一个大顶堆（升序排序）
- 排序：反复将堆顶最大元素与末尾元素交换，然后对堆顶做一次向下调整（sift-down），堆的规模减 1，直到堆中只剩一个元素
整体思路可以概括为：建堆 → 取顶 → 调整 → 取顶 → 调整 → ... → 有序。
交互可视化
通过下方的交互动画，你可以逐步观察堆排序的执行过程：
操作详解
堆的概念
堆是一棵完全二叉树，满足以下性质之一：
- 大顶堆（最大堆）：每个结点的值 ≥ 其左右孩子的值，即
A[i] ≥ A[2i+1]且A[i] ≥ A[2i+2] - 小顶堆（最小堆）：每个结点的值 ≤ 其左右孩子的值，即
A[i] ≤ A[2i+1]且A[i] ≤ A[2i+2]
⭐ 下标关系（数组从 0 开始）：
| 关系 | 公式 |
|---|---|
| 结点 i 的父结点 | (i - 1) / 2 |
| 结点 i 的左孩子 | 2i + 1 |
| 结点 i 的右孩子 | 2i + 2 |
若数组从 1 开始存储，则父结点为
i/2，左孩子为2i，右孩子为2i+1。408 真题中两种编号均有出现，务必注意题目约定。
建堆过程
建堆采用**自底向上的向下调整（sift-down）**策略：从最后一个非叶子结点开始，依次向前对每个结点执行 sift-down。
最后一个非叶子结点的下标为 n/2 - 1（数组从 0 开始）。
c
// 向下调整：将以 i 为根的子树调整为大顶堆
// A[] 为数组，n 为堆的元素个数
void SiftDown(int A[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && A[left] > A[largest])
largest = left;
if (right < n && A[right] > A[largest])
largest = right;
if (largest != i) {
swap(A[i], A[largest]);
SiftDown(A, n, largest); // 继续向下调整
}
}
// 建堆：从最后一个非叶子结点到根，依次 sift-down
void BuildMaxHeap(int A[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
SiftDown(A, n, i);
}⭐ 建堆的时间复杂度为 O(n)，不是 O(n log n)。直觉上看似每个结点都做了 O(log n) 的调整，但大部分结点位于树的底层、调整距离很短。通过数学证明（对每层结点数 × 调整高度求和），总操作次数为 O(n)。这是 408 选择题常考的知识点。
⚠️ 易错：建堆的时间复杂度是 O(n)，不是 O(n log n)。虽然每次调整是 O(log n)，但从最后一个非叶结点到根的调整总和是 O(n)（数学证明可用等比级数）。408 填空题直接考过这个结论。
排序过程
在大顶堆上进行升序排序：
- 将堆顶元素
A[0]（当前最大值）与堆的最后一个元素A[n-1]交换 - 堆的规模减 1（最后一个位置已归位）
- 对新的堆顶
A[0]执行 sift-down，恢复堆性质 - 重复上述步骤，直到堆中只剩一个元素
c
void HeapSort(int A[], int n) {
BuildMaxHeap(A, n); // 第一步：建堆
for (int i = n - 1; i > 0; i--) {
swap(A[0], A[i]); // 堆顶与当前末尾交换
SiftDown(A, i, 0); // 对堆顶做向下调整，堆规模为 i
}
}堆的插入与删除
插入：将新元素追加到堆的末尾，然后执行向上调整（sift-up），依次与父结点比较并交换，直到满足堆性质。时间复杂度 O(log n)。
c
// 向上调整（大顶堆）
void SiftUp(int A[], int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (A[i] > A[parent]) {
swap(A[i], A[parent]);
i = parent;
} else {
break;
}
}
}删除堆顶：将堆顶与最后一个元素交换，堆规模减 1，然后对新堆顶执行 sift-down。时间复杂度 O(log n)。
⭐ 注意：用sift-up 逐个插入的方式建堆，时间复杂度为 O(n log n)，不如自底向上 sift-down 建堆的 O(n) 高效。408 真题曾考过两种建堆方式的区别。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n log n) | 任何情况下都需要完整的建堆 + 调整过程 |
| 最坏时间 | O(n log n) | 与输入序列无关 |
| 平均时间 | O(n log n) | 三种情况均为同一量级 |
| 空间复杂度 | O(1) | 原地排序，仅需常数级辅助空间 |
| 稳定性 | 不稳定 | 堆顶与末尾交换会打乱相同元素的相对顺序 |
⭐ 堆排序是所有比较类排序中少数在最坏情况下仍能保持 O(n log n) 的算法（快排最坏为 O(n²)），但实际运行中由于缓存不友好，常数因子较大。
⚠️ 易错：堆排序是不稳定排序。反例：{1a, 1b, 2}，建大根堆后交换可能颠倒 1a 和 1b 的顺序。
考研高频考点
- ⭐ 建堆的时间复杂度为 O(n) 而非 O(n log n)（选择题/判断题高频陷阱）
- ⭐ 堆排序是不稳定排序（简答题对比各排序算法必考）
- ⭐ 堆排序空间复杂度 O(1)，属于原地排序（与归并排序 O(n) 对比）
- ⭐ 父子结点下标关系（从 0 或从 1 开始两种情况，选择题/填空题常考）
- ⭐ Top-K 问题：从 n 个元素中选出前 K 大/小，建一个大小为 K 的小顶/大顶堆，时间 O(n log K)（算法设计题常见应用）
- 在大顶堆中插入/删除一个元素后，画出调整后的堆（手工模拟题）
- 给定序列判断是否为堆，或画出建堆的中间过程（选择题/填空题）
- 堆排序 vs 快速排序 vs 归并排序的综合比较（简答题）
相关知识
- 堆是一种特殊的完全二叉树，理解其性质需要参考树与二叉树的基本概念
- 堆排序的 O(1) 空间 + O(n log n) 最坏时间与归并排序形成互补：归并稳定但需要 O(n) 空间，堆排序不稳定但原地
- 堆也可用于实现优先队列，这是 Dijkstra 堆优化的基础
- 建堆过程中的"下沉调整"与删除堆顶后的调整完全相同——掌握一个就掌握了两个