《算法导论》第六章 堆排序 保姆级学习笔记

本文约3000字，继续阅读《算法导论》第6章，当年在选修的《数据结构》这门课老师讲二叉树时，听得只想睡觉，什么也没听懂。今天结合AI用大白话方式整理成笔记，一起学习理解下堆排序算法。

关注公众号, 即可获得与Linux相关的电子书籍(含《算法导论》以及数据结构相关)以及常用开发工具，文末有文档清单。

堆排序作为经典的高效排序算法，时间复杂度能稳定在 O (n log n)，还能原地排序不占额外空间，不管是面试还是实际开发都超实用。但很多人一看到 “堆” “完全二叉树” 就头大，其实堆排序的核心逻辑超简单 —— 先把数据变成 “大顶堆”（或小顶堆），再把堆顶的最大值（或最小值）一个个 “揪出来”，最后凑成有序数组。今天用大白话 + 实例拆解，零基础也能秒懂！

一 堆排序 3 个核心概念

在学堆排序前，先分清 3 个关键名词，不用死记定义，看例子就懂：

[1]. 堆：一种 “特殊的完全二叉树”

堆本质是完全二叉树（除了最后一层，其他层都排满，最后一层从左到右依次排列），但有两个硬性要求：

大顶堆：每个父节点的值 ≥ 子节点的值（堆顶是整个树的最大值）；

小顶堆：每个父节点的值 ≤ 子节点的值（堆顶是整个树的最小值）。

堆排序常用大顶堆，咱们后面全以大顶堆为例。

实例：什么是大顶堆？

比如数组 [50, 45, 40, 20, 25, 35, 30]，对应的完全二叉树长这样：

        50（堆顶，最大值）      /    \    45      40   /  \    /  \  20  25  35  30

每个父节点（50、45、40）都比子节点大，这就是标准大顶堆；如果数组是 [30, 25, 35, 20, 45, 40, 50]，对应的树不符合 “父节点≥子节点”，就不是大顶堆。

[2]. 堆的 “数组映射”：不用真的建树

实际实现时，不用专门构建二叉树，直接用数组就能表示堆，核心是 “父子节点的下标关系”：

假设父节点的下标是 i（从 0 开始或从 1 开始都可以，这里以 0 为例）；

左子节点下标 = 2*i + 1；

右子节点下标 = 2*i + 2；

父节点下标 = (子节点下标 - 1) // 2（整除）。

实例：数组和堆的对应关系

还是 [50, 45, 40, 20, 25, 35, 30]，下标 0-6：

下标 0（50）的左子节点：20+1=1（45），右子节点：20+2=2（40）；

下标 1（45）的左子节点：21+1=3（20），右子节点：21+2=4（25）；

下标 2（40）的左子节点：22+1=5（35），右子节点：22+2=6（30）；

下标 3（20）没有子节点（2*3+1=7 超过数组长度 7）。

记住这个下标关系，后面操作堆全靠它！

[3]. 堆排序的核心逻辑：3 步搞定排序

堆排序就 3 个核心步骤，像 “筛选最大值→重建堆→重复” 的循环：

建堆：把原始数组转换成大顶堆（这是最关键的一步）；

交换堆顶和堆尾：把堆顶的最大值（数组第一个元素）和堆尾元素交换，此时堆尾就是 “当前最大值”，相当于把最大值放到了最终位置；

调整堆：交换后堆的结构被破坏，需要把剩下的元素重新调整成大顶堆，然后重复步骤 2，直到所有元素都排好序。

简单说：先把数据 “堆化”，再一个个把最大值 “摘” 出来，最后剩下的就是有序数组。

二 堆排序的 2 个核心操作：建堆 + 调整堆

堆排序的代码实现，核心就是两个函数：调整堆（Heapify） 和 建堆（BuildHeap），咱们逐个拆解。

[1]. 调整堆（Heapify）

假设我们有一个 “几乎是大顶堆” 的结构，只有某个父节点比子节点小，调整堆 就是把这个父节点 “往下沉”，直到它符合 “父节点≥子节点” 的规则。

操作步骤（以大顶堆为例）：

给定一个父节点下标 i，先找到它的左、右子节点；

从父节点、左子节点、右子节点中，选出最大值的下标，记为 max_idx；

如果 max_idx 不是父节点 i（说明子节点比父节点大），就交换父节点和 max_idx 对应的元素；

交换后，原来的父节点可能在新位置上仍比子节点小，所以要递归（或循环）对新位置继续调整，直到整个子树符合大顶堆规则。

实例：调整堆的过程

假设数组 [40, 45, 50, 20, 25, 35, 30]，对应的堆结构：

        40（父节点 i=0，不合格，比子节点 50 小）      /    \    45      50（左子节点 i=1，右子节点 i=2）   /  \    /  \  20  25  35  30

调整步骤：

父节点 i=0，左子节点 45（i=1），右子节点 50（i=2）；

三者最大值是 50（i=2），max_idx=2 ≠ 0，交换 i=0 和 i=2 的元素，数组变成 [50, 45, 40, 20, 25, 35, 30]；

交换后，原来的 40 到了 i=2 的位置，检查它的子节点（i=5 和 6，值 35 和 30），40≥35 和 30，无需再调整，调整完成，堆变成标准大顶堆。

[2]. 建堆（BuildHeap）：把普通数组变成大顶堆

建堆的核心思路：从最后一个非叶子节点开始，从后往前逐个调用 调整堆 函数，直到整个数组变成大顶堆。

关键：最后一个非叶子节点的下标

完全二叉树中，最后一个非叶子节点的下标 = (数组长度 - 2) // 2（因为最后一个节点的下标是 len (arr)-1，它的父节点就是最后一个非叶子节点）。

实例：把普通数组建成大顶堆

原始数组 [30, 25, 35, 20, 45, 40, 50]（长度 7），建堆过程：

计算最后一个非叶子节点下标：(7-2)//2 = 2（对应元素 35）；

从 i=2 开始，从后往前调整：

第一步：调整 i=2（元素 35）。它的子节点是 i=5（40）和 i=6（50），最大值是 50（i=6），交换 35 和 50，数组变成 [30, 25, 50, 20, 45, 40, 35]；

第二步：调整 i=1（元素 25）。它的子节点是 i=3（20）和 i=4（45），最大值是 45（i=4），交换 25 和 45，数组变成 [30, 45, 50, 20, 25, 40, 35]；

第三步：调整 i=0（元素 30）。它的子节点是 i=1（45）和 i=2（50），最大值是 50（i=2），交换 30 和 50，数组变成 [50, 45, 35, 20, 25, 40, 30]；交换后 i=2 的元素 30 可能不合格，继续调整 i=2：它的子节点是 i=5（40）和 i=6（30），最大值是 40（i=5），交换 35 和 40，最终数组变成 [50, 45, 40, 20, 25, 35, 30]，对应的堆是标准大顶堆。

三 堆排序完整实例：一步步看数组如何变有序

以原始数组 [30, 25, 35, 20, 45, 40, 50] 为例，完整演示堆排序过程（目标：从小到大排序）：

步骤 1：建堆（已完成）

建成的大顶堆对应的数组：[50, 45, 40, 20, 25, 35, 30]（堆顶 50 是最大值）。

步骤 2：交换堆顶和堆尾，调整堆（循环执行）

堆排序的核心循环：每次把堆顶最大值放到堆尾，再调整剩下的元素为大顶堆，直到堆为空。

第一次循环（数组长度 7）：

交换堆顶（i=0，50）和堆尾（i=6，30），数组变成 [30, 45, 40, 20, 25, 35, 50]；

此时堆尾 50 已确定是最大值，放到了最终位置，接下来只需要处理前 6 个元素 [30, 45, 40, 20, 25, 35]；

调整前 6 个元素为大顶堆：

父节点 i=0（30），子节点 i=1（45）、i=2（40），最大值 45（i=1），交换 30 和 45，数组变成 [45, 30, 40, 20, 25, 35, 50]；

继续调整 i=1（30），子节点 i=3（20）、i=4（25），30≥20 和 25，调整完成，前 6 个元素的大顶堆是 [45, 30, 40, 20, 25, 35]。

第二次循环（数组长度 6）：

交换堆顶（i=0，45）和堆尾（i=5，35），数组变成 [35, 30, 40, 20, 25, 45, 50]；

堆尾 45 确定是第二大值，处理前 5 个元素 [35, 30, 40, 20, 25]；

调整前 5 个元素为大顶堆：

父节点 i=0（35），子节点 i=1（30）、i=2（40），最大值 40（i=2），交换 35 和 40，数组变成 [40, 30, 35, 20, 25, 45, 50]；

调整 i=2（35），无子节点（2*2+1=5 超过 5），调整完成，前 5 个元素的大顶堆是 [40, 30, 35, 20, 25]。

第三次循环（数组长度 5）：

交换堆顶（40）和堆尾（25），数组变成 [25, 30, 35, 20, 40, 45, 50]；

处理前 4 个元素 [25, 30, 35, 20]，调整为大顶堆 [35, 30, 25, 20]。

第四次循环（数组长度 4）：

交换堆顶（35）和堆尾（20），数组变成 [20, 30, 25, 35, 40, 45, 50]；

处理前 3 个元素 [20, 30, 25]，调整为大顶堆 [30, 20, 25]。

第五次循环（数组长度 3）：

交换堆顶（30）和堆尾（25），数组变成 [25, 20, 30, 35, 40, 45, 50]；

处理前 2 个元素 [25, 20]，调整为大顶堆 [25, 20]。

第六次循环（数组长度 2）：

交换堆顶（25）和堆尾（20），数组变成 [20, 25, 30, 35, 40, 45, 50]；

所有元素处理完毕，数组已从小到大排序！

四 堆排序的特点：优点 + 缺点 + 适用场景

[1]. 优点：

时间复杂度稳定：不管输入数据是有序、逆序还是随机，最坏 / 平均 / 最好情况都是 O (n log n)，比冒泡排序、插入排序（O (n²)）快得多；

空间复杂度低：原地排序，只需要 O (1) 的额外空间（用于交换元素）；

可用于 Top-K 问题：比如找数组中前 10 个最大值，不用全排序，建一次大顶堆，再取 10 次堆顶即可，时间复杂度 O (n + k log n)，比全排序高效。

[2]. 缺点：

不稳定排序：比如数组 [50, 45, 45, 20]，排序后可能变成 [20, 45, 50, 45]（两个 45 的相对位置变了）；

对小规模数据不友好：常数因子比插入排序大，比如排序 10 个元素，插入排序可能比堆排序快。

[3]. 适用场景：

大规模数据排序（比如 10 万、100 万条数据）；

Top-K 问题（比如找前 10 个最热商品、前 5 个最高分）；

内存受限场景（原地排序，不占额外空间）。

五 核心代码实现（C语言版）

结合上面的逻辑，用 C语言写堆排序代码如下：

#include<stdio.h>/** * 调整堆：把以i为父节点的子树调整为大顶堆 * @param arr 待调整的数组 * @param n   当前堆的有效长度（需要处理的元素个数） * @param i   要调整的父节点下标（从0开始） */

void heapify(int arr[], int n, int i) {    while (1) {        int largest = i;        int left = 2 * i + 1;        int right = 2 * i + 2;        if (left < n && arr[left] > arr[largest]) {            largest = left;        }        if (right < n && arr[right] > arr[largest]) {            largest = right;        }        if (largest == i) {            // 父节点已是最大值，无需调整，退出循环            break;        }        // 交换元素        int temp = arr[i];        arr[i] = arr[largest];        arr[largest] = temp;        // 更新i为交换后的下标，继续循环调整        i = largest;    }}/** * 堆排序核心函数（从小到大排序） * @param arr 待排序的数组 * @param n   数组长度 */void heapSort(int arr[], int n) {    // 第一步：构建大顶堆    // 从最后一个非叶子节点开始，从后往前逐个调整    int startIdx = (n - 2) / 2; // 最后一个非叶子节点的下标（关键！）    for (int i = startIdx; i >= 0; i--) {        heapify(arr, n, i);    }    // 第二步：循环交换堆顶和堆尾，再调整堆    for (int i = n - 1; i > 0; i--) {        // 1. 交换堆顶（最大值）和当前堆尾元素        int temp = arr[0];        arr[0] = arr[i];        arr[i] = temp;        // 2. 调整剩下的i个元素为大顶堆（堆长度变为i）        heapify(arr, i, 0);    }}/** * 辅助函数：打印数组 * @param arr 要打印的数组 * @param n   数组长度 */void printArray(int arr[], int n) {    for (int i = 0; i < n; i++) {        printf("%d ", arr[i]);    }    printf("\n");}// 主函数：测试堆排序int main() {    // 测试数组（和之前例子一致，方便对比）    int arr[] = {30, 25, 35, 20, 45, 40, 50};    // 计算数组长度（总字节数 / 单个元素字节数）    int n = sizeof(arr) / sizeof(arr[0]);    printf("原始数组：");    printArray(arr, n);    // 执行堆排序    heapSort(arr, n);    printf("排序后数组：");    printArray(arr, n);    return 0;}

六 常见问题

[1].下标从 0 还是 1 开始？两种都可以，核心是父子节点的下标关系要对应，比如从 1 开始的话，左子节点 = 2i，右子节点 = 2i+1，别搞混；

[2].建堆时为什么从最后一个非叶子节点开始？因为叶子节点没有子节点，本身就是 “合格的堆”，不用调整，从后往前调整效率更高；

[3].调整堆时为什么要递归？因为交换后父节点可能在新位置仍不符合规则，需要继续下沉，直到满足大顶堆要求；

[4].堆排序是稳定排序吗？不是！如果数组有重复元素，相对位置可能会变，这是堆排序的固有特性。

总结

堆排序的核心就两件事：“建堆” 和 “调整堆”。

记住 “大顶堆堆顶是最大值”，通过 “交换堆顶和堆尾 + 调整堆” 的循环，就能把最大值一个个放到最终位置，最后得到有序数组。它的时间复杂度稳定在 O (n log n)，是处理大规模数据的利器，而且代码逻辑不复杂，只要搞懂父子节点的下标关系和调整逻辑，就能轻松实现。