【算法图解】堆排序：用堆来排序

堆排序（Heap Sort）是一个很“工程”的排序：

• 时间：稳定 $O(n\log n)$
• 空间：$O(1)$ 原地
• 缺点：不稳定，常数较大

如果你遇到“内存紧张、不能开辅助数组”的场景，它就很有价值。

1. 先把堆想清楚：完全二叉树 + 堆性质

用数组表示堆时：

• 父节点 i
• 左子 2i+1
• 右子 2i+2

最大堆（Max Heap）满足：

• 任意父节点 >= 子节点

因此：

• 堆顶永远是最大值

2. 堆排序的两步

1. 建堆：把无序数组变成最大堆
2. 反复取最大值：把堆顶（最大）与末尾交换，然后对堆顶做下沉恢复堆性质

3. 核心操作：下沉（siftDown）

function siftDown(a, start, end) {
  let root = start

  while (true) {
    const left = root * 2 + 1
    if (left > end) break

    let swap = root
    if (a[swap] < a[left]) swap = left

    const right = left + 1
    if (right <= end && a[swap] < a[right]) swap = right

    if (swap === root) return

    ;[a[root], a[swap]] = [a[swap], a[root]]
    root = swap
  }
}

4. 建堆：从最后一个父节点开始下沉

function heapify(a) {
  const n = a.length
  const lastParent = Math.floor((n - 2) / 2)
  for (let i = lastParent; i >= 0; i--) {
    siftDown(a, i, n - 1)
  }
}

建堆的复杂度是 $O(n)$（这是很多人容易误背的点）。

5. 完整实现（可运行）

function heapSort(arr) {
  const a = arr.slice()
  heapify(a)

  for (let end = a.length - 1; end > 0; end--) {
    ;[a[0], a[end]] = [a[end], a[0]]
    siftDown(a, 0, end - 1)
  }

  return a
}

console.log(heapSort([4, 10, 3, 5, 1]))

6. 复杂度与性质

• 时间：$O(n\log n)$
• 空间：$O(1)$（原地）
• 稳定性：不稳定

为什么不稳定？

• 交换堆顶与末尾会把相等元素的相对顺序打乱。

7. 面试回答模板

• 堆排序先建最大堆，堆顶是最大值。
• 每次把堆顶与末尾交换，缩小堆范围，对堆顶下沉恢复堆。
• 时间 $O(n\log n)$，空间 $O(1)$，不稳定。

总结

堆排序的价值在于：

• $O(n\log n)$ 的上界稳定
• 又能原地排序

代价是：不稳定 + 常数大。