堆排序如何工作？

Question

堆排序如何工作？

IT Interview Practice · Accepted Answer

**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 元素。

它强化了这样一个观点：正确的数据结构使算法高效。

思想

例子

相关问题

复杂度

何时使用 / 缺陷

为什么这很重要