困难通用10 分钟3,433 字

堆排序

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

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

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

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

  • 大根堆​​:每个节点的值都大于等于​它的左右孩子节点的值,所以根节点是最大值。
  • 小根堆​​:每个节点的值都小于等于​它的左右孩子节点的值,所以根节点是最小值。

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

堆排序分两步走:

  1. 建堆​——把乱序的数组变成一个大根堆。
  2. 排序​——反复把堆顶(最大值)与最后一个元素交换,然后缩小堆的范围,再调整堆。

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


第一步:建堆(Build Heap)——从“小领导”开始调整

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

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

如何找到最后一个非叶子节点?​ 如果数组下标从0开始,有 nnn 个元素,那么最后一个非叶子节点的下标是 n/2−1n/2 - 1n/2−1(整数除法)。因为最后一个元素的下标是 n−1n-1n−1,它的父节点就是最后一个非叶子节点。

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

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

用代码实现的下沉函数(大根堆)通常长这样:

python
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] 对应的大根堆如下图:

       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++ 实现

cpp
#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 实现

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)是快速排序和堆排序混合使用(内省排序)。


相关知识点指引

学会堆排序后,你还可以深入了解:

  • 堆的基本操作​​(插入、删除堆顶、建堆)——堆排序依赖于这些。
  • 优先队列​——堆是实现优先队列的经典数据结构,堆排序就是优先队列的一个应用。
  • 堆排序 vs 快速排序 vs 归并排序​——理解它们各自的优点和缺点,有助于在真实问题中选择最合适的算法。
  • 二叉堆的数组表示​​:堆通常用数组存储,掌握下标关系(父节点 i 的孩子是 2i+1 和 2i+2)是必备技能。

你可以试着用堆排序给班级考试成绩排序,或者给游戏中的得分排行榜排序。动手写一写,调一调,你就能真正掌握这个既经典又实用的算法!

同类知识点