堆排序详解：原理、代码与时间复杂度

通俗地说，思路是什么

堆排序是找最大值的方式更快的选择排序。选择排序每次扫描整个未排序部分，代价是 O(n)。堆排序把未排序部分维护成一个堆，所以最大值始终在下标 0，取出它之后恢复顺序只需 O(log n)。

二叉堆存放在一个普通数组中，不需要指针。对下标 i 处的元素：

• 左孩子在 2*i + 1，右孩子在 2*i + 2；
• 父节点在 (i - 1) // 2；
• 在大顶堆中，每个父节点都大于或等于它的子节点，所以最大元素位于下标 0。

1. 从最后一个非叶节点开始，一路到下标 0，对每个非叶节点执行下沉，由数组建成大顶堆。
2. 把根（最大值）与堆的最后一个元素交换。该元素此时已在最终位置。
3. 把堆缩小一个元素，并让新的根下沉，直到重新满足堆的性质。
4. 重复第 2、3 步，直到堆中只剩一个元素。

逐步演示

对 [4, 10, 3, 5, 1] 排序。竖线之后的元素已有序且已确定。

Python 实现

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

Python 的 heapq 模块在普通列表上提供小顶堆。依次弹出所有元素就能得到有序列表，这是一个简短的（非原地的）堆排序：

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

时间与空间复杂度

自底向上建堆是 O(n)，而不是 O(n log n)，因为完全二叉树中各节点高度之和是 O(n)。总耗时主要由取出阶段决定。

堆排序与其他排序算法的比较

堆排序不稳定：把根交换到末尾，可能让一个元素越过键相同的其他元素。它的主要优势是同时具备 O(n log n) 的最坏情况保证和 O(1) 的额外空间，这是快速排序和归并排序都做不到的组合。它的弱点在于内存访问：在下标 i 与 2*i + 1 之间来回跳转，对 CPU 缓存很不友好，因此通常比实现良好的快速排序慢。Introsort 在快速排序递归过深时，会用堆排序作为后备。

变体与常见错误

• 部分排序：只想得到最大的 k 个元素时，建好堆后取出 k 次，复杂度为 O(n + k log n)。Python 的 heapq.nlargest 和 heapq.nsmallest 就是这么做的。
• 数据流中的 Top-k：维护一个大小为 k 的小顶堆，对每个新元素入堆或替换，时间 O(n log k)，内存 O(k)。
• 自底向上堆排序先把空位一路下沉到叶子，再向上调整，可以节省比较次数。
• Smoothsort 是 Dijkstra 提出的基于堆的变体，对已有序的输入可达 O(n)，但因为实现复杂而很少使用。

何时使用堆排序

当你需要有保证的 O(n log n) 最坏情况，同时不能使用额外内存时，例如在嵌入式或实时系统中，或者作为另一种排序内部的安全后备，就用堆排序。在日常 Python 代码中请用 sorted()，它是稳定的，在典型数据上更快。堆这种数据结构本身比排序更有用：优先队列、Dijkstra 最短路径、调度器、合并 k 个有序列表（heapq.merge）以及求最大的 k 个值，都建立在它之上。面试常考堆的下标公式、为什么建堆是 O(n)，以及 Top-k 问题。