Hello 算法之堆排序：基于大顶堆的原地 O(n log n) 排序原理与多语言实现

堆排序（Heap Sort）是《Hello 算法》排序章节中“基于堆数据结构的 O(n log n) 排序算法”。本篇以 堆排序 文档为主体，完整梳理其算法流程（建堆、交换首尾、堆化修复、循环 n-1 轮），并结合仓库中 Python 实现 与 C++ 实现 的源码，深入讲解 sift_down() 为什么必须引入堆长度参数 n、建堆阶段为何是 O(n) 而非 O(n log n)，以及堆排序“时间 O(n log n)、空间 O(1)、非稳定”三大特性的成因。读完本篇，你可以从零手写一个原地堆排序，并准确解释它的复杂度与稳定性问题。

从“小顶堆 + 辅助数组”到“大顶堆 + 原地交换”

堆排序是一种基于堆数据结构实现的高效排序算法。最直观的思路分两步：

1. 输入数组并建立小顶堆，此时最小元素位于堆顶；
2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

以上方法虽然可行，但需要借助一个额外数组来保存弹出的元素，比较浪费空间。因此实际实现中通常采用一种更加优雅的方式：直接利用原数组建立大顶堆，反复把堆顶最大值“挪”到数组末尾。这样既不需要额外数组，也能保持原地排序。

仓库中“堆”章节的 MaxHeap.pop() 出堆操作恰好揭示了这两者的关系：出堆本身就是“交换根节点与最右叶节点 → 删除节点 → 从顶至底堆化”三步。堆排序只是把其中的“删除节点”这一步省掉了——用“收缩堆的有效长度”代替物理删除，从而把弹出元素天然地落在原数组的末尾，形成已排序后缀。文档中的提示也指出：元素出堆操作本身就包含交换首尾与堆化两步，只是多了一个弹出元素的步骤。

算法流程

设数组的长度为 n，堆排序的完整流程如下：

1. 输入数组并建立大顶堆。完成后，最大元素位于堆顶；
2. 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 1，已排序元素数量加 1；
3. 从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复；
4. 循环执行第 2 步和第 3 步。循环 n - 1 轮后，即可完成数组排序。

整个过程可以概括为“建堆一次、收缩 n-1 次”。建堆完成后，数组左半部分是未排序的堆，右半部分是已排序区；每轮循环把当前堆的最大值沉入已排序区边界，再通过堆化把堆性质恢复。

核心源码解析

sift_down()：带长度参数的从顶至底堆化

在代码实现中，堆排序复用了“堆”章节中相同的从顶至底堆化 sift_down() 函数。值得特别注意的是：由于堆的长度会随着提取最大元素而减小，因此需要给 sift_down() 添加一个长度参数 n，用于指定堆的当前有效长度。这一点在 Python 实现 中体现得非常清晰：

def sift_down(nums: list[int], n: int, i: int):
    """堆的长度为 n ，从节点 i 开始，从顶至底堆化"""
    while True:
        # 判断节点 i, l, r 中值最大的节点，记为 ma
        l = 2 * i + 1
        r = 2 * i + 2
        ma = i
        if l < n and nums[l] > nums[ma]:
            ma = l
        if r < n and nums[r] > nums[ma]:
            ma = r
        # 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if ma == i:
            break
        # 交换两节点
        nums[i], nums[ma] = nums[ma], nums[i]
        # 循环向下堆化
        i = ma

从源码结构看，这里的关键有两处：

• 左右子节点索引按堆（完全二叉树的数组表示）计算：左子节点 2 * i + 1、右子节点 2 * i + 2，与 MaxHeap 中的 left()、right() 完全一致；
• 边界判断使用 l < n、r < n 而不是 l < len(nums)。若缺少 n 参数，堆化会“越界”到已排序区，破坏已排好的后缀，排序结果直接错误。

heap_sort()：建堆与排序两个阶段

Python 版 heap_sort() 全文只有两个循环，逻辑非常紧凑：

def heap_sort(nums: list[int]):
    """堆排序"""
    # 建堆操作：堆化除叶节点以外的其他所有节点
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    # 从堆中提取最大元素，循环 n-1 轮
    for i in range(len(nums) - 1, 0, -1):
        # 交换根节点与最右叶节点（交换首元素与尾元素）
        nums[0], nums[i] = nums[i], nums[0]
        # 以根节点为起点，从顶至底进行堆化
        sift_down(nums, i, 0)

逐行对应算法流程：

• 建堆阶段：从最后一个非叶节点 len(nums) // 2 - 1 开始倒序遍历，对每个节点执行从顶至底堆化。倒序遍历保证了堆化某节点时，其子树已经是合法的子堆，因此一次堆化即可修复整棵子树。叶节点没有子节点，天然就是合法子堆，无须堆化，所以起点是“最后一个节点的父节点”；
• 排序阶段：外层循环 i 从 len(nums) - 1 递减到 1，恰好 n - 1 轮。每轮先交换 nums[0] 与 nums[i]，把当前最大值放到已排序区边界；再调用 sift_down(nums, i, 0)，注意这里传入的有效堆长度是 i 而非 len(nums)——上一轮交换进来的 nums[i] 已经不属于堆；
• 循环结束时，下标 0 处剩下最后一个元素，与下标 1 处相邻，数组即为升序。

C++ 实现 与 Python 版逐语句对应：siftDown() 使用 l < n && nums[l] > nums[ma] 的短路条件做边界保护，heapSort() 同样分为 nums.size() / 2 - 1 倒序建堆与 n - 1 轮“swap + siftDown”两个阶段。仓库中 Java、C#、JavaScript、TypeScript、Go、Rust、Swift、Ruby、Kotlin、Dart 等各语言目录下均有同构的 heap_sort 文件，可对照阅读。

建堆为什么是 O(n)？

文档的复杂度结论是“建堆操作使用 O(n) 时间”，这个结论并非显然——如果对 n 个元素逐个“入堆”（每次 O(log n)），建堆就是 O(n log n)。仓库中 建堆操作 一节给出了更严格的推导，值得展开：

• 需要堆化的节点只有非叶节点，数量为 n / 2（整除）；
• 一个节点从顶至底堆化的最大迭代次数等于它到叶节点的距离，即节点高度，最大为树高 log n；
• 朴素地把两者相乘会高估为 O(n log n)，但这忽略了“底层节点数量远多于顶层节点”的性质。

精确算法是假设一棵高度为 h 的完美二叉树，对每一层“节点数量 × 节点高度”求和：

$$T(h) = 2^0 h + 2^1 (h-1) + 2^2 (h-2) + \dots + 2^{(h-1)} \times 1$$

用错位相减法（将上式乘以 2 再相减）化简，可得 $T(h) = 2^{h+1} - h - 2 = O(2^h)$；而完美二叉树的节点数 $n = 2^{h+1} - 1$，故 $T(h) = O(n)$。

结论：输入列表并建堆的时间复杂度为 O(n)。 这也解释了源码中建堆循环为什么能直接对原数组倒序遍历一次完成——叶节点天然合法、每层节点数按 2 的幂增长，使得总堆化代价被 O(n) 主导。Python 标准库的 heapq.heapify() 同样利用了这一点，heap.py 的注释明确写明：“输入列表并建堆，时间复杂度为 O(n)，而非 O(nlogn)”。

算法特性与复杂度分析

结合源码结构，文档给出的三大特性可以逐一落实：

• 时间复杂度为 O(n log n)、非自适应排序：建堆 O(n)；排序阶段每轮堆化的代价为 O(log n)（堆化路径最长为树高），共 n - 1 轮，合计 O(n log n)。排序开销完全由堆的高度决定，与输入元素的初始有序程度无关，因此堆排序是非自适应排序——即使输入近乎有序，也不会像插入排序那样退化加速；
• 空间复杂度为 O(1)、原地排序：从源码看，heap_sort() 只使用了几个索引变量（i、l、r、ma），没有申请辅助数组；元素交换和堆化全部在原数组上进行。这与“小顶堆 + 记录弹出元素”的初版思路相比，正是“更加优雅的实现方式”省下的那部分空间；
• 非稳定排序：稳定性要求相等元素的相对顺序在排序后保持不变。而堆排序每轮都把堆顶与堆底交换，且堆化过程中元素会沿树向下跳跃交换，两个相等元素完全可能因为处于不同分支而被交换先后，因此相等元素的相对位置可能发生变化，堆排序不是稳定排序。

运行验证

各语言示例均以相同的驱动代码验证正确性。以 heap_sort.py 为例：

"""Driver Code"""
if __name__ == "__main__":
    nums = [4, 1, 3, 1, 5, 2]
    heap_sort(nums)
    print("堆排序完成后 nums =", nums)

输入 [4, 1, 3, 1, 5, 2] 排序完成后输出 堆排序完成后 nums = [1, 1, 2, 3, 4, 5]。注意样例中特意包含两个相等的 1，可以直观地观察非稳定性：排序后两个 1 的相对位置由交换过程决定，并不保证与输入一致。C++ 版 heap_sort.cpp 使用同一组数据 [4, 1, 3, 1, 5, 2] 输出 堆排序完成后 nums = [1, 1, 2, 3, 4, 5]。

小结

堆排序是“堆”数据结构最典型的工程化应用，其精髓在于三点：

1. 原地化：用“交换首尾 + 收缩有效长度”替代“弹出元素存入辅助数组”，把 O(n) 额外空间压缩到 O(1)；
2. 长度参数：sift_down(nums, n, i) 中的 n 是堆当前有效长度，是正确性关键——边界判断 l < n、r < n 保证堆化永不越界到已排序区；
3. 复杂度画像：建堆 O(n)（靠倒序遍历 + 层级加和的精确推导），排序 O(n log n)，空间 O(1)，代价是非稳定、非自适应。

与快速排序同为 O(n log n) 量级相比，堆排序的优势在于最坏情况仍然 O(n log n)、空间 O(1)；劣势则在于常数因子较大、缓存局部性较差，且不稳定。这也是仓库中同时收录归并、快排、堆排等多种 O(n log n) 算法的意义：实际选型需要结合稳定性、最坏性能与内存约束综合权衡。