堆排序：像整理扑克牌一样高效排序

同学们，你们有没有试过整理一副乱糟糟的扑克牌？假如你要按从小到大的顺序排好，最快的办法之一是这样：先把所有牌摆成一个小根堆（最小的牌在最上面），然后每次拿走最上面的牌（也就是最小的那张），再把剩下的牌重新调整成堆。重复这个过程，拿出来的牌就自动从小到大排好了。这个思路，就是堆排序的核心思想。

堆排序是一种原地排序算法——它不需要额外的内存空间（除了几个临时变量），就能直接在你原来的数组上完成排序。它的时间复杂度是 $O(n \log n)$ ，而且最坏情况下也稳定在这个复杂度，不像快速排序那样可能退化到 $O(n^2)$ 。所以当你需要一个稳定高效的排序方法时，堆排序是个可靠的选择。

堆排序的核心思想：利用“堆”这个数据结构

要理解堆排序，首先得知道什么是堆。堆是一种特殊的完全二叉树，分为两种：

大根堆：每个节点的值都大于等于它的左右孩子节点的值，所以根节点是最大值。
小根堆：每个节点的值都小于等于它的左右孩子节点的值，所以根节点是最小值。

堆排序通常使用大根堆来实现升序排序（从小到大）。为什么呢？因为我们可以反复从堆顶拿出最大值，放到数组末尾，最后数组就变成升序了。就像你从一堆乱牌中每次找出最大的那张，放到最右边，最后整副牌就从小到大排好了。

堆排序分两步走：

建堆——把乱序的数组变成一个大根堆。
排序——反复把堆顶（最大值）与最后一个元素交换，然后缩小堆的范围，再调整堆。

下面我详细解释每一步，并用生活例子帮你记住。

第一步：建堆（Build Heap）——从“小领导”开始调整

假如你是一个班长，要组织全班同学按身高从高到低排成一个大根堆（高的当根）。但是全班同学现在乱站成一排（对应无序数组）。你怎么做最快？

你不需要从第一个同学开始调整，而是从最后一个非叶子节点（也就是有孩子的“小领导”）开始，逐个向前检查。为什么从后往前？因为调整一个节点时，你需要保证它的左右子树已经都是堆了。从后往前，就能保证当你调整到某个节点时，它的孩子子树已经调整好了。

如何找到最后一个非叶子节点？ 如果数组下标从0开始，有 $n$ 个元素，那么最后一个非叶子节点的下标是 $n/2 - 1$ （整数除法）。因为最后一个元素的下标是 $n-1$ ，它的父节点就是最后一个非叶子节点。

下沉操作（Sift Down）——让“不称职”的节点往下走

调整一个节点是否“称职”，靠的是下沉操作。比如你发现一个“小领导”身高比他的两个孩子都矮（不满足大根堆），那就让他和最高的孩子交换位置，然后继续检查他是否在新的位置上仍然比新孩子们矮，直到他坐到合适的位置。

用代码实现的下沉函数（大根堆）通常长这样：

def sift_down(arr, n, index):
    """
    大根堆下沉操作
    arr: 数组（堆），n: 当前堆的大小，index: 需要调整的节点下标
    """
    while True:
        left = 2 * index + 1   # 左孩子下标
        right = 2 * index + 2  # 右孩子下标
        largest = index        # 记录当前最大值的下标，先假设是父节点

        # 和左孩子比
        if left < n and arr[left] > arr[largest]:
            largest = left
        # 和右孩子比
        if right < n and arr[right] > arr[largest]:
            largest = right

        # 如果最大值不是父节点，就交换，继续下沉
        if largest != index:
            arr[index], arr[largest] = arr[largest], arr[index]
            index = largest
        else:
            break  # 父节点已是最大，结束

你可以把 largest 想象成一个“身高测量仪”，它先指向父节点，然后和两个孩子比，谁身高高就指向谁。最后如果测量仪指向的不是父节点，说明父节点需要和孩子换位置。

完整建堆过程

假设数组 [4, 10, 3, 5, 1]，我们把它建成大根堆。

数组长度 n=5，最后一个非叶子节点下标 = 5//2 - 1 = 1（值是10）。
从下标1开始：节点10的孩子是5和1，10比他们都大，不需要调整。
再往前到下标0（值4）：它的孩子是10和3。10最大，所以4和10交换 → 数组变成 [10, 4, 3, 5, 1]。
现在4来到下标1的位置，它的孩子是5和1。5更大，所以4和5交换 → 数组变成 [10, 5, 3, 4, 1]。
下标2（值3）调整？但它的孩子下标5、6已经超过堆大小，所以不用调整。

建堆完成！最终数组 [10, 5, 3, 4, 1] 对应的大根堆如下图：

第二步：排序（Heap Sort）——每次拿走最大的牌

建好大根堆后，最大值10就在堆顶。现在我们要把它放到数组的最后（升序排序）。怎么做？

把堆顶10和最后一个元素1交换 → 数组变成 [1, 5, 3, 4, 10]。
然后堆的大小减1（忽略已经排好的10），在剩下的 [1, 5, 3, 4] 中，对新的堆顶1执行下沉操作：
- 1的下标0，孩子是5和3 → 1和5交换 → [5, 1, 3, 4]
- 1的下标1，孩子是4（下标3）和？右孩子下标2（值3）已过？注意此时堆大小是4，所以孩子下标12+1=3（值4）和12+2=4（超出，忽略）。1和4交换 → [5, 4, 3, 1]
现在堆顶是5，交换堆顶5与当前堆的最后一个元素（下标3，值1） → [1, 4, 3, 5, 10]，堆大小再减1（忽略5和10）。
下沉1：与较大的孩子4交换 → [4, 1, 3, 5, 10]
交换堆顶4与当前堆最后一个（下标2，值3） → [3, 1, 4, 5, 10]
堆大小再减1，剩下 [3, 1]。3已经是堆顶，且3大于1，无需下沉。
交换堆顶3与最后一个1 → [1, 3, 4, 5, 10]
堆大小只剩1，结束。

最终得到 [1, 3, 4, 5, 10]，升序排序完成。

每一步你可以想象成：你有一堆乱牌，你每次从堆顶拿走最大的那张，放到右边，剩下的牌重新调整成堆，这样最后就从小到大排好了。

新手容易犯的错误

1. 建堆的循环范围搞错

很多人写成 for i in range(n-1, -1, -1) 或者 for i in range(n//2, -1, -1)。正确的是从 n//2 - 1 到 0。因为只有有孩子的节点才需要下沉。叶子节点（下标 >= n//2）没有孩子，直接跳过。

2. 排序时忘记缩小堆大小

交换堆顶和最后一个元素后，一定要把堆大小减1，否则排好的元素又会参与下沉，打乱顺序。在代码里，下沉时传递的 n 应该等于当前堆的元素个数（已排序的不算）。

3. 下沉时左右孩子下标越界

一定要先检查 left < n 和 right < n，否则会访问到已经排好的元素或者越界。

4. 混淆大根堆和小根堆与排序顺序的关系

通常：用大根堆实现升序（每次把最大值放到末尾）；用小根堆实现降序（每次把最小值放到末尾）。但反过来也可以，比如大根堆也可以实现降序：把堆顶最大值放到数组开头？实际上堆排序默认是交换到末尾，所以用大根堆是升序。如果你想要降序，可以建小根堆，把最小值放到末尾，最后数组是降序（因为最小值最后放，大的在前面）。

5. 忘记堆排序是不稳定的

堆排序不稳定。比如你有一组分数 [90, 80, 80]，其中两个80可能因为下沉交换而改变相对顺序。如果你需要稳定排序，用归并排序。

完整可运行代码（C++ 和 Python）

下面两份代码都包含了详细注释和测试用例。

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

// 下沉操作（大根堆）
void siftDown(vector<int>& arr, int n, int index) {
    while (true) {
        int left = 2 * index + 1;   // 左孩子下标
        int right = 2 * index + 2;  // 右孩子下标
        int largest = index;        // 记录最大值的下标，先假设是父节点

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(arr[index], arr[largest]);  // 交换父节点和较大的孩子
            index = largest;                 // 继续下沉
        } else {
            break;  // 已经满足大根堆性质
        }
    }
}

// 堆排序主函数
void heapSort(vector<int>& arr) {
    int n = arr.size();  // 数组长度

    // 1. 建堆：从最后一个非叶子节点开始向前下沉
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, n, i);
    }

    // 2. 排序：重复交换堆顶和末尾，缩小堆，下沉新堆顶
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);      // 将最大值放到数组末尾
        siftDown(arr, i, 0);       // 堆大小变为 i，调整新堆顶
    }
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {4, 10, 3, 5, 1, 7, 9, 2, 6, 8};  // 乱序数组
    cout << "原始数组: ";
    printArray(arr);

    heapSort(arr);

    cout << "排序后数组: ";
    printArray(arr);
    return 0;
}

Python 实现

def sift_down(arr, n, index):
    """大根堆下沉操作"""
    while True:
        left = 2 * index + 1   # 左孩子下标
        right = 2 * index + 2  # 右孩子下标
        largest = index        # 记录最大值下标，先假设是父节点

        if left < n and arr[left] > arr[largest]:
            largest = left
        if right < n and arr[right] > arr[largest]:
            largest = right

        if largest != index:
            arr[index], arr[largest] = arr[largest], arr[index]  # 交换
            index = largest  # 继续下沉
        else:
            break

def heap_sort(arr):
    n = len(arr)  # 数组长度

    # 1. 建堆
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

    # 2. 排序
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 交换堆顶和当前末尾
        sift_down(arr, i, 0)             # 堆大小变为 i，调整新堆顶

# 测试
arr = [4, 10, 3, 5, 1, 7, 9, 2, 6, 8]  # 乱序数组
print("原始数组:", arr)
heap_sort(arr)
print("排序后数组:", arr)

运行结果：

原始数组: [4, 10, 3, 5, 1, 7, 9, 2, 6, 8]
排序后数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

堆排序的性能和适用场景

指标	说明
时间复杂度	建堆 O(n)，排序 O(n log n)，总 O(n log n)，且最坏也是 O(n log n)
空间复杂度	O(1)（原地排序，只用了几个临时变量）
稳定性	不稳定（相同元素可能交换顺序）
适用场景	当你有巨大的数据，且需要稳定的 O(n log n) 时间复杂度时（比如嵌入式系统、实时系统），堆排序很合适。它也常用于实现优先队列。

如果你比较一下：快速排序平均很快，但最坏情况会退化；归并排序稳定且时间复杂度稳定，但需要额外 O(n) 空间。堆排序是“中庸之选”——时间稳定、空间不额外，但常数较大（下沉操作比快速排序的划分慢一点）。所以实际中，很多语言的排序库（如C++的std::sort）是快速排序和堆排序混合使用（内省排序）。

堆排序