堆排序¶

堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的比较排序算法。它结合了选择排序的思想与完全二叉树的结构优势，具有 O(n log n) 的时间复杂度，且是原地排序（in-place），空间复杂度为 O(1)。

一、堆的基本概念回顾¶

二叉堆：一种近似完全二叉树的结构，分为：
最大堆（Max Heap）：父节点 ≥ 子节点
最小堆（Min Heap）：父节点 ≤ 子节点
数组表示：对于下标从 0 开始的数组：
节点 i 的左孩子：2*i + 1
节点 i 的右孩子：2*i + 2
父节点：(i - 1) / 2

二、C语言实现：最大堆排序（升序排列）¶

✅ 核心思路：¶

构建最大堆（从最后一个非叶子节点向上调整）
将堆顶（最大值）与末尾元素交换
堆大小减一，重新调整堆
重复步骤2-3直到堆只剩一个元素

✅ 完整可运行代码（注释完善，简洁易记）¶

C
/**
 * 向下调整堆（维护最大堆性质）
 * @param arr: 数组指针
 * @param n: 当前堆的大小
 * @param i: 当前调整的父节点索引
 */
void heapify(int arr[], int n, int i) {
    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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);  // 递归调整子树
    }
}

/**
 * 堆排序主函数（升序）
 * @param arr: 待排序数组
 * @param n: 数组长度
 */
void heapSort(int arr[], int n) {
    // 第一步：构建最大堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 第二步：逐个提取堆顶元素放到末尾
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大值（根）与末尾交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 重新调整剩余元素为最大堆
        heapify(arr, i, 0);
    }
}

三、代码解析与关键点说明¶

模块	功能
`heapify`	维护以 `i` 为根的子树的最大堆性质，时间复杂度 O(log n)
`heapSort`	先建堆 O(n)，再排序 O(n log n)
构建堆	从 `n/2 - 1` 开始（最后一个非叶节点）向前遍历

💡 为什么从 n/2 - 1 开始？ - 因为叶子节点无需调整（无子节点） - 最后一个非叶子节点是 (n-1) 的父节点：(n-1-1)/2 = n/2 - 1

四、时间复杂度分析¶

步骤	时间复杂度	说明
构建堆	O(n)	虽然每个节点调用 heapify 是 O(log n)，但利用数学推导可得整体为 O(n)
排序过程	O(n log n)	每次交换后调用 heapify，共 n-1 次，每次 O(log n)
总时间复杂度	O(n log n)	最好、最坏、平均情况一致

📌 堆排序的时间复杂度稳定，不依赖输入数据分布。

五、空间复杂度与稳定性¶

属性	值	说明
空间复杂度	O(1)	原地排序，仅使用常量额外空间
稳定性	❌ 不稳定	相同元素可能因交换改变相对位置
比较次数	多于快速排序	实际运行速度通常慢于快排
适用场景	内存受限、需稳定性能	不适合小数据集

六、堆排序的变体实现（拓展）¶

1. 最小堆实现（降序排序）¶

只需修改 heapify 中的比较方向：

C
void min_heapify(int arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] < arr[smallest])
        smallest = left;
    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    if (smallest != i) {
        int temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;
        min_heapify(arr, n, smallest);
    }
}

调用方式相同，最终得到降序排列。

2. 迭代式 heapify（避免递归开销）¶

C
void heapify_iterative(int arr[], int n, int i) {
    while (i < n) {
        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 = largest;  // 继续向下调整
    }
}

⚠️ 优点：节省栈空间，适合嵌入式系统或大堆
⚠️ 缺点：代码略复杂，但性能更优

3. 堆排序模板（泛型支持）¶

使用函数指针支持任意类型（如字符串、结构体）：

C
typedef int (*compare_func)(const void*, const void*);

void heapify_generic(void* base, size_t size, int n, int i, compare_func cmp) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    // 使用字节偏移模拟数组访问（简化版略）
    // 实际中可用 memcpy 和指针运算实现
    // 此处仅示意思想
}

🧩 类似 qsort() 的设计思路，提升通用性。

七、相关知识拓展¶

1. 堆的应用场景¶

应用	说明
优先队列	堆是优先队列的标准实现（如任务调度、Dijkstra算法）
Top-K 问题	找最大/最小的 k 个数，用最小/最大堆维护
中位数维护	双堆法（最大堆 + 最小堆）动态求中位数
外部排序	多路归并中的归并优化（败者树、堆优化）

2. 与其他排序对比¶

算法	平均时间	最坏时间	空间	稳定性	适用场景
快速排序	O(n log n)	O(n²)	O(log n)	否	一般场景，快
归并排序	O(n log n)	O(n log n)	O(n)	是	需稳定排序
堆排序	O(n log n)	O(n log n)	O(1)	否	内存紧张、性能稳定要求高
插入排序	O(n²)	O(n²)	O(1)	是	小数据集

✅ 堆排序优势：时间稳定 + 空间小
❌ 劣势：常数因子大，缓存不友好

3. 实际应用举例¶

Linux 内核调度器：使用红黑树和堆管理进程优先级
图像处理：边缘检测中找前K大梯度值
游戏开发：技能冷却系统按时间排序（最小堆）
流数据处理：实时统计 Top 10 热门商品（堆维护）

八、可视化理解（mermaid图示）¶

graph TD
    A[原始数组: 4,10,3,5,1] --> B[构建最大堆]
    B --> C[10,5,3,4,1]
    C --> D[交换10↔1, 堆size--]
    D --> E[调整堆 → 5,4,3,1]
    E --> F[交换5↔1 → 4,1,3]
    F --> G[继续...]
    G --> H[最终有序: 1,3,4,5,10]

九、背诵要点（口诀记忆）¶

🔁 “建堆下沉，换顶再沉”
📏 “父(i), 左(2i+1), 右(2i+2)”
🧠 “从n/2-1往回走，每次heapify不能漏”
⏱️ “O(n log n)稳如狗，空间只用O(1)”

十、总结¶

特性	值
时间复杂度	O(n log n)（稳定）
空间复杂度	O(1)（原地排序）
稳定性	不稳定
是否比较排序	是
实用性	中等（理论价值高）
可扩展性	高（可用于优先队列等）

✅ 适合背诵版本：第一个递归 heapify + 两次循环的 heapSort 结构清晰，逻辑严密，易于理解和默写。