堆排序里最容易被误解的一句话是：建堆复杂度是 O(n)，不是 O(n log n)。如果把每个元素都当成一次向下调整，确实容易以为总成本是 n 次 log n。关键在于多数节点离叶子很近，真正能下沉很多层的节点很少。本文用反直觉辟谣的方式拆 Heapify，并给出可运行 Java 代码。
堆排序相关文章在 CSDN 算法频道靠前并不意外。堆既出现在排序，也出现在优先队列、Top K、调度器和图算法里。但很多人学完后仍然卡在一个问题：heapify 从最后一个非叶子节点往前调整，每个节点最坏下沉 log n，那建堆不应该是 O(n log n) 吗？
这个推理看似合理，错在把所有节点都当成了根节点。反直觉的地方在于：堆里越多的节点越靠近底层，而底层节点下沉不了几步。
谣言一：建堆等于 n 次插入
如果从空堆开始，一个个插入元素，每次向上调整，建成堆确实是 O(n log n)。但 Heapify 不是这么做的。Heapify 从数组原地出发，把最后一个非叶子节点到根节点逐个 siftDown。叶子节点天然是堆，不需要动。
两种方式得到的都是堆，路线不同，复杂度也不同。
谣言二：每个节点都会下沉 log n 层
只有根节点最多下沉 log n 层。根下面一层的节点最多下沉 log n - 1 层。越往下，节点数量翻倍，但可下沉高度减少。到了倒数第二层，节点很多，却最多只下沉 1 层；叶子节点最多下沉 0 层。
把成本按高度分组：高度为 0 的节点约 n/2 个，成本 0；高度为 1 的节点约 n/4 个，成本 1；高度为 2 的节点约 n/8 个，成本 2。总和近似是：
n/4 * 1 + n/8 * 2 + n/16 * 3 + ...
这个级数收敛到 O(n)。所以建堆不是“每个节点都 log n”，而是“大量节点几乎不用动”。
一份可运行 Java 代码
下面实现最大堆排序，排序结果为升序。建堆阶段从最后一个非叶子节点 n/2 - 1 开始，排序阶段每次把堆顶最大值换到末尾，再缩小堆范围。
import java.util.Arrays;
public class HeapifyDemo {
static void heapSort(int[] nums) {
int n = nums.length;
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(nums, i, n);
}
for (int end = n - 1; end > 0; end--) {
swap(nums, 0, end);
siftDown(nums, 0, end);
}
}
private static void siftDown(int[] nums, int root, int size) {
while (true) {
int left = root * 2 + 1;
int right = root * 2 + 2;
int largest = root;
if (left < size && nums[left] > nums[largest]) {
largest = left;
}
if (right < size && nums[right] > nums[largest]) {
largest = right;
}
if (largest == root) {
return;
}
swap(nums, root, largest);
root = largest;
}
}
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private static void assertSorted(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
throw new AssertionError("not sorted: " + Arrays.toString(nums));
}
}
}
public static void main(String[] args) {
int[][] tests = {
{
5, 1, 1, 9, 0, -3, 7},
{
},
{
42},
{
3, 2, 1},
{
-1, -5, -2, -2}
};
for (int[] test : tests) {
heapSort(test);
assertSorted(test);
}
int[] sample = {
5, 1, 1, 9, 0, -3, 7};
heapSort(sample);
System.out.println(Arrays.toString(sample));
System.out.println("Heapify tests passed");
}
}
测试输出：
[-3, 0, 1, 1, 5, 7, 9]
Heapify tests passed
复杂度分析
建堆阶段是 O(n)。排序阶段执行 n-1 次取堆顶，每次 siftDown 最多走堆高，时间复杂度是 O(n log n)。所以整个堆排序仍然是 O(n log n)，只是其中的建堆不是瓶颈。
空间复杂度是 O(1)，因为排序在原数组上进行，没有额外开数组。注意递归版 siftDown 会带来调用栈，本文用循环写法，空间更直观。
边界条件
空数组和单元素数组不需要调整，循环自然跳过。重复元素不会破坏排序，只要比较条件保持一致即可。负数和正数没有区别，因为堆只关心比较大小。siftDown 的边界是当前堆大小 size，不是数组总长度；排序阶段末尾已经放好的元素不能再参与堆调整。
常见错误
第一，把最后一个非叶子节点写成 n / 2，通常不会错得很明显，但会多处理一个叶子节点。正确起点是 n / 2 - 1。第二，排序阶段交换堆顶和末尾后，仍然用 n 作为堆大小，结果会把已排序区又卷回来。第三，只比较左孩子不比较右孩子，最大堆性质无法保证。第四，以为建堆 O(n) 就代表堆排序整体 O(n)，这是把两个阶段混在了一起。
可复制测试用例
代码里的测试覆盖了普通数组、空数组、单元素、逆序数组和负数重复数组。你还可以加入 {2, 2, 2}，确认重复值不会触发死循环；加入 {Integer.MAX_VALUE, 0, Integer.MIN_VALUE}，确认比较逻辑没有依赖加减法，从而避免整数溢出。
手算一轮：为什么从中间开始
假设数组长度是 7，下标从 0 到 6。下标 0 的孩子是 1 和 2，下标 1 的孩子是 3 和 4，下标 2 的孩子是 5 和 6。下标 3、4、5、6 都没有孩子，它们天然满足堆性质。所以第一个需要处理的节点是 2，也就是 n / 2 - 1。
从 2 往 0 处理还有一个隐含好处：当你调整某个节点时，它的左右子树已经是堆。siftDown 的前提正是“两个孩子子树已经可靠，只需要把当前 root 放到合适位置”。如果顺序反过来，从根开始调，下面还乱着，调完根也无法保证整体成立，后面子树变化还可能破坏根的选择。
拿 {5, 1, 1, 9, 0, -3, 7} 举例。先处理下标 2，值为 1，孩子是 -3 和 7，它会和 7 交换。再处理下标 1，值为 1，孩子是 9 和 0，它会和 9 交换。最后处理下标 0，值为 5，孩子是 9 和 7，它先和 9 交换，再看新的孩子。短短几步后，最大值被推到根，两个子树也保持最大堆。
Heapify 和优先队列的关系
堆排序用 Heapify 是为了原地排序。优先队列也用堆，但目标不一样：它关心频繁插入和取最值，而不一定要把所有元素排好序。Java 的 PriorityQueue 默认是小根堆，poll() 每次取最小值；本文手写的是最大堆，因为把最大值放到数组末尾后，最终得到升序。
如果你要解决 Top K 问题，也不一定要堆排序。找最大的 K 个元素时，常见做法是维护一个大小为 K 的小根堆。新元素比堆顶大才替换，时间复杂度是 O(n log K)，当 K 远小于 n 时比全量排序更合适。这说明堆不是只有“排序”一种用法，它更像一种动态维护极值的工具。
稳定性和原地性的取舍
堆排序的优点是原地、最坏情况仍为 O(n log n)，不像快速排序那样依赖划分质量。缺点是它不是稳定排序：相等元素的相对顺序可能改变。对于只排数字这无所谓；如果排的是订单、日志、用户记录，而相等键下还要保留原始顺序，就要额外保存原始下标，或者换用稳定排序。
它的缓存友好性也一般。siftDown 会在数组里按树形下标跳跃访问，不如归并或快速排序那样在局部连续区间内操作。很多语言标准库没有直接用堆排序作为通用排序默认实现，就是因为真实性能不只看大 O，还看常数、分支预测和内存访问模式。
调试 Heapify 的一个小技巧
写错堆代码时，不要只看最终数组是否有序。建议在建堆结束后单独检查堆性质：对每个下标 i，如果左孩子存在，nums[i] >= nums[left]；如果右孩子存在，nums[i] >= nums[right]。这样能把“建堆错了”和“排序阶段错了”分开。
如果排序结果偶尔错，多半是 size 边界问题；如果建堆后根不是最大值，多半是孩子比较或下沉循环问题。把两个阶段拆开断言，定位会快很多。
什么时候选堆排序，什么时候别选
堆排序适合你需要稳定的最坏时间上界，又不想额外开大数组的场景。它不会像朴素快速排序那样在极端输入上退化到平方级，也不像归并排序那样天然需要 O(n) 额外空间。嵌入式环境、内存紧张的批处理、小型基础库练习，都适合用它理解原地排序的边界。
但在多数业务代码里，直接使用语言标准库排序更合适。标准库通常对多种输入形态做了大量优化，并处理了稳定性、对象比较、局部有序数据等细节。自己手写堆排序的主要价值，是在需要优先队列、Top K、调度器时理解底层机制，而不是替代成熟库函数。
还有一点要分清：堆排序每轮都会把当前最大值放到最终位置，所以它适合一次性得到完整有序数组；如果你只需要不断取最大或最小，优先队列更直接；如果你只需要第 K 大，快速选择或小根堆通常更省。算法选择的关键不是名字熟不熟，而是输出需求到底是什么。
总结
Heapify 的线性复杂度来自堆的形状，不来自某个隐藏技巧。底层节点数量多但移动少，高层节点移动多但数量少，合起来就是 O(n)。真正决定堆排序总复杂度的，是后续反复取堆顶的 n log n。把建堆和排序阶段分开看，很多关于堆的误解就会自然消失。
