3.4 堆排序
这一节，你能解决什么问题
学完这一节，你能够：
- 理解堆的结构和堆序性质，知道为什么"父节点 ≥ 子节点"就够了
- 分析堆排序的复杂度，理解"建堆为什么是 Θ(n)"这个反直觉结论
- 判断什么时候该用堆排序，理解"原地 + 最坏保证"的独特价值
- 审查 agent 给出的堆实现，发现隐藏的 O(n log n) 假设错误
问题情境
某嵌入式系统团队接到一个棘手的需求：
- 内存只有 2KB
- 需要排序功能
- 不能接受系统崩溃
工程师小王有两个备选方案：
| 方案 | 优点 | 缺点 |
|---|---|---|
| 快排 | 实践中快 | 最坏 Θ(n²)，可能超时崩溃 |
| 归并排序 | 稳定 Θ(n log n) | 需要 Θ(n) 额外空间，内存撑不住 |
小王皱着眉头："就没有两全其美的方案吗？"
答案就在堆排序。
堆排序的独特组合：
- 原地排序：Θ(1) 额外空间
- 最坏保证：Θ(n log n)，没有快排的 Θ(n²) 风险
问题：堆排序是怎么做到的？代价是什么？
直观思路
先理解"堆"是什么。
堆是一个数组，但可以看作一棵完全二叉树。
完全二叉树：除最后一层外，每层都是满的；最后一层从左到右填充。
数组：[16, 14, 10, 8, 7, 9, 3, 2, 4]
树形表示：
16 ← 第 0 层
/ \
14 10 ← 第 1 层
/ \ / \
8 7 9 3 ← 第 2 层
/ \
2 4 ← 第 3 层为什么用数组表示树？
完全二叉树的结构规律，可以用数学公式计算父子关系：
父节点：parent(i) = (i - 1) // 2
左孩子：left(i) = 2 × i + 1
右孩子：right(i) = 2 × i + 2这样，不需要指针，节省空间。
堆序性质：每个父节点 ≥ 所有子节点。
这个性质保证：最大值在根节点（索引 0）。
直觉：堆就像一个金字塔，越大越在上面。拿走最大的，剩下的自动调整。
规范定义
最大堆
结构性质：完全二叉树，用数组紧凑表示
堆序性质：每个节点 ≥ 其子节点
关键洞察：堆序性质只要求"父 ≥ 子"，不要求"左 > 右"或"完全有序"。
为什么这样定义？
因为堆只关心一件事：快速找到最大值。堆序性质保证最大值在根节点。
至于左右孩子的相对大小，不需要维护。这种"最小必要约束"的思想，是高效数据结构设计的关键。
算法实现
堆排序分为两个阶段：
阶段一：建堆
把乱序数组变成堆。
BUILD-MAX-HEAP(A):
for i = len(A)//2 down to 0:
MAX-HEAPIFY(A, i)为什么从 len(A)//2 开始？
因为索引 ≥ len(A)//2 都是叶子节点，天然满足堆序性质。
阶段二：排序
HEAPSORT(A):
BUILD-MAX-HEAP(A) # 建堆 Θ(n)
for i = len(A)-1 down to 1: # n-1 次循环
swap A[0] and A[i] # 最大放末尾
MAX-HEAPIFY(A[0..i-1], 0) # 维护堆性质 Θ(log i)MAX-HEAPIFY：让节点"下沉"
假设一棵树，根节点违反堆序性质（比子节点小），但两棵子树都是合法的堆。
怎么修复？让根节点"下沉"到正确位置。
MAX-HEAPIFY(A, i):
l = left(i)
r = right(i)
largest = i
if l < len(A) and A[l] > A[largest]:
largest = l
if r < len(A) and A[r] > A[largest]:
largest = r
if largest != i:
swap A[i] and A[largest]
MAX-HEAPIFY(A, largest) # 递归下沉一步步执行：
问题：
4 ← 违反：4 < 14 和 4 < 10
/ \
14 10 ← 子树都是合法堆
Step 1：比较 4 和子节点 14、10，14 最大
交换 4 和 14
14
/ \
4 10 ← 4 下沉到位置 1
Step 2：位置 1 的子树可能违反
比较 4 和子节点 8、7，8 最大
交换 4 和 8
14
/ \
8 10
/ \
4 7 ← 4 下沉到位置 3
Step 3：位置 3 是叶子节点，无需继续
结果：合法的最大堆这个方法是怎么想到的
你可能会问：建堆为什么是 Θ(n)，不是 Θ(n log n)？
这是算法分析中的经典反直觉结论。
错误的分析
很多初学者这样分析：
MAX-HEAPIFY 是 Θ(log n)
调用 n/2 次
总时间 = Θ(n log n) ← 错！错在哪里？
错在假设每次 MAX-HEAPIFY 都是 Θ(log n)。
实际上，大部分节点的高度很小！
正确的分析
关键洞察：高度不同的节点，数量不同。
高度为 h 的节点数量 ≤ ⌈n / 2^{h+1}⌉
为什么？
- 高度 0（叶子节点）：约 n/2 个
- 高度 1：约 n/4 个
- 高度 2：约 n/8 个
- ...
- 高度 log n：最多 1 个（根节点）精确计算：
总时间 = Σ_{h=0}^{⌊log n⌋} (高度 h 的节点数) × Θ(h)
≤ Σ_{h=0}^{⌊log n⌋} ⌈n/2^{h+1}⌉ × c×h
≤ c×n × Σ_{h=0}^{∞} h / 2^{h+1}
= c×n × 2 （数学级数求和）
= Θ(n)怎么想到的？
思考过程：
- 朴素想法：每个节点都可能下沉到最底层，Θ(log n)
- 发现问题：叶子节点根本不下沉！
- 更精确：不同高度的节点，下沉深度不同
- 计算：数量 × 高度的加权和
- 数学级数：Σ h/2^h = 2
洞察：不要用最坏情况乘以次数。要分析不同层次的开销。
正确性分析
MAX-HEAPIFY 的正确性
循环不变式：每次递归调用前：
- A[i] 和子节点中最大的交换
- 交换后，子树满足堆序性质
证明：
比较三个节点（当前 + 左右孩子），找到最大的，交换。
交换后，当前位置满足堆序性质。如果子节点位置违反，递归处理。
终止条件：到达叶子节点，或当前节点已经是最大的。
BUILD-MAX-HEAP 的正确性
循环不变式：每次迭代前，A[i+1..n-1] 都满足堆序性质。
证明：
从叶子节点开始（天然满足），自底向上处理。
每次处理一个节点后，以它为根的子树满足堆序性质。
终止时，整个树满足堆序性质。
HEAPSORT 的正确性
循环不变式：每次迭代前：
- A[i..n-1] 已排序（最大的 n-i 个元素）
- A[0..i-1] 是堆，包含剩余 i 个元素
证明：
每次交换堆顶（最大）和末尾，然后维护堆性质。
交换后，A[i] 是剩余元素中最大的。
heapify 后，A[0..i-1] 仍然是堆。
终止时，整个数组已排序。
复杂度分析
建堆
Θ(n)。前面已经详细分析。
排序循环
Σ_{i=1}^{n-1} Θ(log i) = Θ(n log n)总复杂度
Θ(n) + Θ(n log n) = Θ(n log n)
空间复杂度
Θ(1)（只用了几个变量）
什么时候不该用这个方法
该用的情况
- 内存紧张（Θ(1) 额外空间）
- 需要最坏保证（不能接受 Θ(n²)）
- 实时系统（必须保证时间上限）
- 嵌入式设备（资源受限）
不该用的情况
- 一般场景（快排实践中更快，缓存友好）
- 需要稳定性（堆排序不稳定）
- 小数据（Θ(n log n) 的 overhead 不值得）
- 缓存敏感场景（堆排序访问模式对缓存不友好）
与其他排序对比
| 特性 | 堆排序 | 快排 | 归并排序 |
|---|---|---|---|
| 最坏时间 | Θ(n log n) | Θ(n²) | Θ(n log n) |
| 期望时间 | Θ(n log n) | Θ(n log n) | Θ(n log n) |
| 额外空间 | Θ(1) | Θ(log n) | Θ(n) |
| 稳定性 | 不稳定 | 不稳定 | 稳定 |
| 缓存友好 | 不友好 | 友好 | 中等 |
选择指南：
- 堆排序：内存受限 + 不能接受 Θ(n²) 最坏
- 快排：一般场景（实践中最快）
- 归并：大数据 + 需要稳定 + 有额外空间
本节小结
解决了什么问题？
- 原地排序 + 最坏 Θ(n log n) 保证
- 在"内存紧张 + 不能崩溃"的组合场景，堆排序是独特选择
核心方法是什么？
- 堆结构：完全二叉树 + 堆序性质
- 下沉操作：MAX-HEAPIFY 让节点下沉到正确位置
- 建堆策略：自底向上，利用大部分节点高度小的事实
为什么正确？
- 循环不变式证明三个操作
- 堆序性质保证最大值在堆顶
- 每次交换 + heapify 维护堆性质
代价是什么？
- 时间：Θ(n log n)（建堆 Θ(n)，排序 Θ(n log n))
- 空间：Θ(1)
- 不稳定，缓存不友好
适用场景？
内存受限、需要最坏保证。不适合一般场景（快排更快）。
能否自己使用？
能。关键是理解：
- 堆序性质是"最小必要约束"
- 建堆 Θ(n) 来自"数量 × 高度"加权和
- 堆排序在"原地 + 最坏保证"组合上独特
练习
基本理解
练习 1：对数组 [3, 1, 4, 1, 5, 9, 2, 6]，画出完全二叉树结构，标注每个节点的索引和值。
练习 2：计算数组 [3, 1, 4, 1, 5, 9, 2, 6] 的各高度节点数量，验证建堆 Θ(n) 的计算。
练习 3：对 [5, 3, 17, 10, 84, 19, 6, 22, 9]，完整执行堆排序，记录每次交换和 heapify。
方法应用
练习 4：写出 MAX-HEAPIFY 的循环不变式，并完整证明三步。
练习 5：用最小堆实现堆排序。分析差异：需要哪些修改？
错误诊断
练习 6：以下建堆实现有什么问题？
def build_heap_bug(A):
for i in range(len(A)): # ← 这里
heapify(A, i)分析：为什么这样是 Θ(n log n)？应该怎么改？
练习 7：为什么堆排序不稳定？给出一个反例。
方案比较
练习 8：分析三种 Θ(n log n) 排序的适用场景：
| 场景 | 应该用哪个？ | 理由 |
|---|---|---|
| 内存 2KB，不能崩溃 | ||
| 大数据，需要稳定 | ||
| 一般 Web 服务 | ||
| 实时系统，必须保证时间 |
开放设计
练习 9：Top-k 问题。
设计一个算法，从 n 个元素中选出最大的 k 个。比较两种方案：
- 排序后取前 k：Θ(n log n)
- 维护 k 大小的最小堆：Θ(n log k)
分析：k << n 时，哪个更好？
练习 10：建堆 Θ(n) 验证。
让 agent 写两种建堆实现：
- 自顶向下（逐个插入）：Θ(n log n)
- 自底向上：Θ(n)
对比实际运行时间，验证理论分析。
上一节：3.3 分治排序
下一节：3.5 线性时间排序