21、堆排序：建堆过程、堆排序算法实现、堆排序的时间复杂度分析
堆排序，说实话，是我个人非常喜欢的一种排序算法。它不像快速排序那样有「最坏情况」的焦虑，也不像归并排序那样需要额外的大块内存。你想想看，它能在原地完成排序，时间复杂度还稳定在 O(n log n)，这在工程中其实很讨喜。
我记得刚入行那会儿，有个嵌入式项目需要在资源受限的芯片上做数据排序。快速排序递归太深，容易爆栈；归并排序又吃内存。最后我选了堆排序，稳稳地跑过了压力测试。从那以后，我对堆排序就多了一份信任。
21.1 什么是堆？
堆，本质上是一棵完全二叉树。但它有个特殊约束：每个父节点的值，都大于等于（或小于等于）它的子节点。
- 大顶堆：父节点 ≥ 子节点。堆顶是最大值。
- 小顶堆：父节点 ≤ 子节点。堆顶是最小值。
堆排序用的是大顶堆。为什么呢？因为每次把堆顶（最大值）换到数组末尾，然后缩小堆的范围，重复操作，就能得到升序序列。说白了，就是「每次挑最大的，放到最后面」。
核心要点：堆排序 = 建堆 + 反复调整堆。
21.2 建堆过程
建堆，就是把一个无序数组调整成堆结构。我习惯从最后一个非叶子节点开始，从下往上做「下沉」操作。
为什么从下往上？因为这样可以保证：当我处理某个节点时，它的左右子树已经是堆了。这样我只需要把这个节点「沉」到合适的位置就行。
最后一个非叶子节点的索引怎么找？对于长度为 n 的数组（索引从 0 开始），最后一个非叶子节点是 n/2 - 1。
我的小技巧：建堆时别从上往下做，那样效率低。从下往上，每个节点只下沉一次，时间复杂度 O(n)。
建堆的伪代码逻辑是这样的：
// 从最后一个非叶子节点开始，逐个下沉
for (i = n/2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}其中 heapify 就是下沉操作：把当前节点和它的左右子节点比较，如果子节点更大，就交换，然后继续下沉。
21.3 堆排序算法实现
堆排序分两步走：
- 建堆：把无序数组建成大顶堆。
- 排序：把堆顶元素和末尾元素交换，然后堆大小减 1，再对新的堆顶做下沉调整。重复直到堆大小为 1。
下面是我写的一个完整实现，注释写得比较细，你可以直接拿去用：
#include <stdio.h>
// 下沉操作：维护大顶堆性质
void heapify(int arr[], int n, int i) {
int largest = i; // 先假设当前节点最大
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点更大，更新 largest
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点更大，更新 largest
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果 largest 不是 i，说明需要交换
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归下沉被换下去的节点
heapify(arr, n, largest);
}
}
// 堆排序主函数
void heapSort(int arr[], int n) {
// 第一步：建堆（从下往上）
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 第二步：排序（逐个取出堆顶）
for (int i = n - 1; i > 0; i--) {
// 把堆顶（最大值）换到末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 对新的堆顶做下沉，堆大小减 1
heapify(arr, i, 0);
}
}我曾经踩过的坑：写 heapify 时，递归调用忘记传正确的堆大小。如果你在排序阶段传了完整的 n，而不是当前的 i，那已经排好的元素会被重新拉回堆里，排序就全乱了。切记：排序阶段每次 heapify 的堆大小是 i，不是 n。
21.4 堆排序的时间复杂度分析
我们来拆开算：
| 阶段 | 时间复杂度 | 说明 |
|---|---|---|
| 建堆 | O(n) | 从下往上，每个节点下沉次数和它的高度有关，总和是 O(n) |
| 排序 | O(n log n) | 需要执行 n-1 次交换，每次下沉 O(log n) |
| 总复杂度 | O(n log n) | 建堆 + 排序，取大头 |
你可能会问：建堆为什么是 O(n) 而不是 O(n log n)？
嗯，这里有个数学小陷阱。直觉上，每个节点下沉一次是 O(log n)，n 个节点就是 O(n log n)。但别忘了，下层节点多但高度小，上层节点少但高度大。算下来，所有节点的下沉次数之和其实是线性的。具体推导你可以去看《算法导论》的摊还分析，这里不展开。
另外，堆排序的 空间复杂度是 O(1)，它是在原地排序的。这一点在内存紧张的场景下非常香。
21.5 堆排序 vs 其他排序
我整理了一张对比表，方便你直观感受：
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
堆排序的优点是「稳」——不管数据长什么样，它都是 O(n log n)。缺点是不稳定，而且实际运行中常数比快速排序大一些。所以大部分通用排序库（比如 C 的 qsort）还是用快速排序。但在实时系统或嵌入式场景下，堆排序的确定性更让人放心。
21.6 堆排序的核心流程图
下面这张 SVG 图，把堆排序的完整流程画出来了。从无序数组开始，到建堆，再到排序，一目了然。
21.7 总结与避坑
堆排序的核心就三句话：
- 建堆从下往上，时间复杂度 O(n)。
- 排序阶段每次交换后做一次下沉，共 n-1 次，O(n log n)。
- 空间复杂度 O(1)，原地排序，不稳定。
我的建议：如果你在面试中手写堆排序，记得先写 heapify 函数，再写主流程。把 heapify 写对了，堆排序就完成了一大半。另外，注意索引从 0 开始还是从 1 开始，这个细节很容易搞混。
好了，堆排序就讲到这里。你可以在自己的机器上跑一跑代码，感受一下建堆和排序的过程。下一章我们会聊另一种树形结构——哈夫曼树，它在数据压缩领域非常有用。