堆排序（Heap Sort）
堆排序的核心不是“排序”本身，而是反复利用堆顶一定是当前最大值这个性质，把最大元素一个个放到数组尾部。
定义
堆排序是一种基于堆数据结构的排序算法。它利用堆这种数据结构的特性：堆顶元素总是最大（最大堆）或最小（最小堆）。
核心思路
- 建堆：将无序数组构建成最大堆（或最小堆）
- 排序：
- 将堆顶元素（最大值）与末尾元素交换
- 堆的大小减1
- 对新堆顶进行下沉操作，恢复堆性质
- 重复以上步骤，直到堆的大小为1
原数组: [4, 10, 3, 5, 1]
建堆: [10, 5, 3, 4, 1] (最大堆)
10
/ \
5 3
/ \
4 1
排序过程:
交换10和1: [1, 5, 3, 4] + [10]
调整堆: [5, 4, 3, 1] + [10]
交换5和1: [1, 4, 3] + [5, 10]
调整堆: [4, 1, 3] + [5, 10]
...
最终: [1, 3, 4, 5, 10]
为什么它能稳定在 O(n log n)
可以把过程拆成两段：
- 建堆：
O(n) - 每次把堆顶换到末尾，再下沉恢复堆：共做
n-1次，每次O(log n)
所以总复杂度稳定落在 O(n log n)，不会像快排那样退化到 O(n^2)。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n log n) | 建堆O(n) + n次调整O(log n) |
| 平均时间 | O(n log n) | 同上 |
| 最坏时间 | O(n log n) | 性能稳定 |
| 空间复杂度 | O(1) | 原地排序 |
| 稳定性 | ❌ 不稳定 | 交换操作破坏相对顺序 |
Go 代码
Go 实现
package main
import "fmt"
func heapify(arr []int, n, i int) {
largest := i
left := 2*i + 1
right := 2*i + 2
if left < n && arr[left] > arr[largest] {
largest = left
}
if right < n && arr[right] > arr[largest] {
largest = right
}
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func heapSort(arr []int) {
n := len(arr)
// 建堆
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// 排序
for i := n - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
fmt.Println("原始数组:", arr)
heapSort(arr)
fmt.Println("排序后:", arr)
}思路展开
2. 堆的数组表示
# 对于索引i的节点（从0开始）：
parent(i) = (i - 1) // 2 # 父节点
left_child(i) = 2 * i + 1 # 左子节点
right_child(i) = 2 * i + 2 # 右子节点易错点
堆排序最容易错的是下标关系和“当前堆大小”。
- 建堆从最后一个非叶子节点开始，不是从根开始。
- 排序阶段每次交换后，堆的有效长度会减少 1。
heapify处理的是“以某个节点为根的子树恢复堆性质”，不是整堆重建。- 堆排序不稳定，别把它和优先队列的功能混为一谈。
经典题目
基础应用
- 排序数组 - LeetCode 912
- 数组中的第K个最大元素 - LeetCode 215
堆的应用
Top K 问题
- 最小的k个数 - 剑指 Offer 40
- 查找和最小的K对数字 - LeetCode 373
优缺点
优点
- ✅ 时间复杂度稳定：保证 O(n log n)
- ✅ 原地排序：只需 O(1) 额外空间
- ✅ 不需要递归（可避免栈溢出）
- ✅ 适合找Top K元素
缺点
- ❌ 不稳定：交换操作破坏相对顺序
- ❌ 实际性能不如快速排序（缓存不友好）
- ❌ 建堆过程复杂
应用场景
- Top K问题：找最大或最小的K个元素
- 优先队列：任务调度、事件驱动
- 时间保证：需要稳定的O(n log n)且空间受限
- 不需要稳定性：对稳定性无要求
堆排序 vs 其他排序
| 特性 | 堆排序 | 快速排序 | 归并排序 |
|---|---|---|---|
| 时间复杂度 | O(n log n) | O(n log n) ~ O(n²) | O(n log n) |
| 空间复杂度 | O(1) | O(log n) | O(n) |
| 稳定性 | 不稳定 | 不稳定 | 稳定 |
| 实际性能 | 中等 | 最快 | 较慢 |
| 最坏保证 | 有 | 无 | 有 |
为什么堆排序实际性能不如快排
- 缓存不友好：堆的操作跳跃访问内存
- 常数因子大：建堆和调整的操作较多
- 分支预测差：比较操作不规律
堆排序的优化
- 使用迭代版下沉：把递归
heapify改成循环，减少函数调用开销，也避免极端输入下的递归深度。 - 从后往前建堆：只需要处理索引
n/2-1到0的非叶子节点，叶子节点天然满足堆性质。 - 按场景选择堆大小：求前
k大时不必完整堆排序，维护大小为k的最小堆即可，复杂度为O(n log k)。 - 不要误追求稳定性：如果需要稳定排序，应优先考虑归并排序或在元素中附带原始下标。