Heap sort 从数组构建一个 binary heap，然后反复提取最大值以产生排序顺序。它在 O(n log n) 时间运行，且是 in-place。
思想
max-heap 将最大元素保持在根部。构建堆（O(n)），然后将根交换到末尾，缩小堆，并重新堆化（sift down）— 重复 n 次。
例子
python
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap in O(n)
return [heapq.heappop(arr) # pop smallest n times
for _ in range(len(arr))]
heap_sort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
经典实现通过在数组内 sift down 来原地执行。
复杂度
- 时间： 所有情况下 O(n log n)。空间： 原地 O(1)。
何时使用 / 缺陷
当你需要 保证 O(n log n) 和 O(1) 额外空间 时使用（merge sort 需要 O(n)；quicksort 有 O(n²) 风险）。它 不稳定 且缓存局部性差，因此在实践中通常比 quicksort 更慢。相同的堆结构驱动 优先队列 和查找前 k 个元素。
为什么这很重要
堆排序是唯一既是最坏情况 O(n log n) 又是原地的常见排序算法，这在内存受限或需要保证界限的设置中非常有价值。
其底层的堆结构用途广泛 — 优先队列、Dijkstra 算法和流式前 k 元素。
它强化了这样一个观点：正确的数据结构使算法高效。