堆排序（Heap Sort）
基于二叉堆结构的原地排序算法，时间复杂度 O(N log N)，空间复杂度 O(1)。
定义
堆排序是从二叉堆结构衍生出来的排序算法，主要分两步：
- 原地建堆（Heapify）：在待排序数组上原地创建二叉堆
- 原地排序（Sort）：将堆顶元素不断取出，最终得到有序结果
堆排序不需要额外的辅助空间，直接在原数组上进行 sink, swim 操作完成排序。
核心特性
| 特性 | 说明 |
|---|---|
| 时间复杂度 | O(N log N) |
| 空间复杂度 | O(1)（原地排序） |
| 稳定性 | 不稳定 |
| 适合场景 | 空间受限、需要保证 O(N log N) 最坏情况 |
基本原理
堆排序基于二叉堆的 sink/swim 操作：
- 建堆（Heapify）：从最后一个非叶子节点开始，向前遍历，对每个节点执行 sink 操作，将无序数组调整为二叉堆
- 排序（Sort）：
- 将堆顶元素（最大/最小）与堆尾元素交换
- 堆的大小减1
- 对新的堆顶执行 sink 操作
- 重复直到堆为空
初始数组: [4, 10, 3, 5, 1]
建堆后: [10, 5, 3, 4, 1] (大顶堆)
排序过程:
交换堆顶与堆尾: [1, 5, 3, 4, 10], 对[1,5,3,4] sink -> [5,4,3,1,10]
交换堆顶与堆尾: [1,4,3,5,10], 对[1,4,3] sink -> [4,1,3,5,10]
...最终得到: [1, 3, 4, 5, 10]
与类似概念对比
| 维度 | 堆排序 | 快速排序 | 归并排序 |
|---|---|---|---|
| 时间复杂度 | O(N log N) | 平均 O(N log N)，最坏 O(N²) | O(N log N) |
| 空间复杂度 | O(1) | O(log N) 递归栈 | O(N) |
| 稳定性 | 不稳定 | 不稳定 | 稳定 |
| 原地排序 | 是 | 是 | 否 |
| 最坏情况 | O(N log N) | O(N²) | O(N log N) |
时间复杂度/性能
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 建堆（Heapify） | O(N) | 从最后一个非叶子节点开始 sink |
| 排序（每次取堆顶） | O(log N) | 每次 sink 操作 |
| 总排序时间 | O(N log N) | N 个元素，每个 O(log N) |
| 空间复杂度 | O(1) | 原地排序，不需要额外空间 |
常见类型/变体
1. 基于大顶堆的升序排序
使用大顶堆，每次将堆顶最大元素交换到末尾，得到升序数组。
2. 基于小顶堆的降序排序
使用小顶堆，每次将堆顶最小元素交换到末尾，得到降序数组。
核心组件
sink（下沉）操作
将节点与子节点比较，如果小于（大顶堆）或大于（小顶堆）子节点，则交换，直到满足堆性质。
swim（上浮）操作
将节点与父节点比较，如果大于（大顶堆）或小于（小顶堆）父节点，则交换，直到满足堆性质。
注意事项
- 学习堆排序算法必须掌握二叉堆结构原理，否则可能完全无法理解排序过程
- 堆排序是不稳定排序（相同元素的相对位置可能改变）
- 建堆的时间复杂度是 O(N)，不是 O(N log N)（因为底层节点高度较小）
- 可以用算法可视化工具观察建堆和排序过程
常见实现
| 实现 | 特点 |
|---|---|
| 递归实现 | 代码简洁，但递归栈有开销 |
| 迭代实现 | 避免递归，直接循环完成 sink/swim |
关键技巧
原地建堆（Heapify）
从最后一个非叶子节点（索引 n/2 - 1）开始，向前遍历，对每个节点执行 sink 操作。
排序过程
排序时，将堆顶与堆尾交换后，需要对新的堆顶执行 sink，但堆的大小要减1（排除已排序的部分）。
应用场景
- 需要 O(N log N) 时间复杂度且空间受限的场景
- 实时系统（保证最坏情况 O(N log N)，不像快速排序可能退化到 O(N²)）
- 内省排序（IntroSort）的组成部分：C++ 的
std::sort结合快速排序、堆排序、插入排序