堆排序

堆排序先把数组组织成最大堆，再反复将堆顶最大值交换到末尾，缩小堆并恢复堆序。最大堆是一棵完全二叉树，每个父节点的值都不小于子节点。堆排序的时间复杂度上界为 O(n log n)，额外空间为 O(1)。

数组本身就能表示完全二叉树：下标 0 是根，下标 i 的两个子节点位于 2i + 1 和 2i + 2。不需要额外指针或树节点。排序过程中，左侧堆区逐步缩小，右侧有序区逐步增长。

堆排序如何建堆和取出最大值

两个阶段都使用 sift_down：找出较大的子节点，如果它比当前节点大，就交换并继续向下检查；否则停止。一次下沉最多经过树高那么多层，交换次数不超过 ⌊log₂ n⌋。

建堆阶段从最后一个父节点 ⌊n/2⌋ − 1 开始，向前处理到根。每次处理父节点时，它下方的子树已经是堆，所以只需让当前节点下沉到合适位置。整个建堆阶段为 O(n)，因为大多数节点靠近树底，最多只能下沉一两层。

排序阶段让 end 从 n − 1 减到 1。先交换根与 arr[end]，把剩余元素中的最大值放到最终位置；再将堆的大小缩为 end，只在这个范围内修复新根。右侧已经排好的部分不再参加比较。

堆排序逐步演示

默认输入为 [38, 12, 56, 7, 41, 23, 5]，n = 7。

建堆从 ⌊7/2⌋ − 1 = 2 开始。下标 2 的值为 56，子节点 23 和 5 都比它小，不交换。下标 1 的值为 12，较大的子节点是 41，交换后 12 到达叶子，数组变为 [38, 41, 56, 7, 12, 23, 5]。最后处理根 38，它与较大的子节点 56 交换；到达新位置后，38 大于子节点 23 和 5，下沉结束。

最大堆为 [56, 41, 38, 7, 12, 23, 5]。这次建堆处理了三个父节点，发生两次交换。

第一次取出最大值时，交换根 56 与 arr[6] = 5。下标 6 从此属于有序区，堆内只剩六个元素。新根 5 先与较大的子节点 41 交换，再与 12 交换。堆变为 [41, 12, 38, 7, 5, 23]，有序尾部为 [56]。

之后依次确定 41、38、23、12、7 的位置。每次先把堆顶交换到边界，再缩小堆并修复；这组输入中，后续每次下沉最多交换一次。最后留下的 5 是最小值，位于下标 0。结果为 [5, 7, 12, 23, 38, 41, 56]。

动画同时展示树形结构和数组，两边对应同一份数据。heap | sorted 分界线每取出一个最大值就向左移动一格，右侧绿色元素不再参与排序。可以再试输入 56, 41, 38, 23, 19, 12, 7：它已经满足最大堆条件，建堆阶段不发生交换。

时间与空间复杂度

建堆为 O(n)，之后执行 n − 1 次取出操作，每次下沉最多为 O(log n)，因此总时间上界为 O(n log n)。本课的 sift_down 使用循环，不需要递归栈，也不需要辅助数组。

表中给出的是上界，并不表示每组输入都做同样多的比较。相等元素可能使下沉提前停止。与快速排序不同，堆排序不会因为连续选到极端基准值而退化到 O(n²)；与归并排序不同，它不需要 O(n) 辅助缓冲区。

代价是稳定性和访存局部性。堆顶与末尾的长距离交换会改变相等元素的顺序；父子节点通过下标跳跃访问，也不像连续扫描那样利于缓存。

边界情况

• 空数组或单元素数组：建堆和取出循环都不执行。
• 逆序输入：已经是最大堆，建堆不交换，但仍需执行后续取出与修复。
• 已经有序：较小元素靠近树根，建堆时可能下沉多层。
• 重复值：严格比较 > 不会因相等而触发下沉交换，但取出阶段仍可能改变相等元素的顺序，堆排序不稳定。

常见错误

• 从根开始向下建堆：子树还不是堆时，只修复父节点不能保证整个区域满足堆序。应从 ⌊n/2⌋ − 1 向前处理。
• 交换后忘记缩小堆：应调用 sift_down(arr, end, 0)，而非继续传入 n，否则已归位的元素又会参加排序。
• 固定选择左子节点：必须先选较大的子节点，否则交换后另一侧仍可能大于父节点。
• 混用下标规则：从 0 开始计数时，子节点是 2i + 1 和 2i + 2，不是 2i。
• 取出循环运行到 end = 0：最后一个元素自然是最小值，处理到 1 就够了。