堆排序

堆排序是利用二叉堆这种数据结构来排序的算法。它把数组视为一棵完全二叉树：a[0] 是根，a[i] 的孩子是 a[2i+1] 和 a[2i+2]，无需额外指针。

思路两步走

1. 建最大堆 (heapify)：从最后一个非叶子节点 i = ⌊n/2⌋ - 1 开始，倒序对每个节点执行 siftDown —— 把它和子节点中最大的那个比较，更大就下沉，直到满足”父节点 ≥ 子节点”。

倒序的好处：当 siftDown 处理到 i 时，它的两棵子树都已经是堆，所以一次下沉就能修复局部。

2. 反复取出堆顶：堆顶 a[0] 永远是最大值。重复以下操作直到只剩一个元素：

• 交换 a[0] 与堆中最后一个元素 a[end]
• 把 end 排除出堆（它已经就位 — 这就是有序区间增长的方向）
• 对新的根 a[0] 再做一次 siftDown，恢复堆性质

siftDown 是核心

while (true) {
  l = 2i+1, r = 2i+2, best = i
  if (l 在堆内 && a[l] > a[best]) best = l
  if (r 在堆内 && a[r] > a[best]) best = r
  if (best == i) break       // 已是局部最大，停止
  swap(a[i], a[best]); i = best
}

每轮 siftDown 最多下沉 log n 层。

复杂度

• 时间：O(n log n)，无论输入分布
• 空间：O(1) — 完全就地，不需要辅助数组
• 稳定：否 — 远距离交换会打乱等值元素的相对顺序

为什么建堆是 O(n) 不是 O(n log n)？常见误解。倒序 siftDown 时，靠近叶子的节点（数量多）下沉路径短，靠近根的节点（数量少）下沉路径长 —— 求和后总开销是 O(n)。但第二阶段每次都从根 siftDown 一次，那是 O(n log n)，所以总体仍是 O(n log n)。

与快排、归并对比

堆排序的卖点：最坏 O(n log n) + 完全就地。但常数大、缓存不友好，实际工程里很少单用，常作为快排的 fallback（IntroSort 在递归深度超过 2·log n 时切到堆排序）。

在动画里看什么

• 上半场（建堆）：从中段倒着开始 siftDown，看每个节点如何”压下去”
• 下半场（排序）：每轮紫色根与末尾交换，被交换出去的格子变绿色（有序），堆的有效范围从右向左缩
• 注意有序区间是从右端长出来的，跟前几种排序不太一样