数据结构与算法：堆排序 (Heap Sort) 详解

堆排序（Heap Sort）是一种基于比较的排序算法，它利用了堆（Heap）这种数据结构来设计。它的主要特点是时间复杂度稳定在 $O(n \log n)$，并且只需要 $O(1)$ 的额外空间（原地排序）。

1. 堆排序的原理

1.1 什么是“堆”？

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

大顶堆 (Max Heap)：每个节点的值都大于或等于其子节点的值。堆顶（根节点）是整个堆中最大的元素。（升序排序使用大顶堆）
小顶堆 (Min Heap)：每个节点的值都小于或等于其子节点的值。堆顶是最小的元素。（降序排序使用小顶堆）

1.2 数组与堆的映射

在实际代码中，我们通常使用数组来存储堆，而不是建立链式二叉树。对于数组中下标为 $i$ 的节点：

父节点索引： $\lfloor \frac{i-1}{2} \rfloor$
左孩子索引： $2i + 1$
右孩子索引： $2i + 2$

1.3 排序流程 (以升序为例)

堆排序主要分为两个阶段：

建堆 (Build Heap)：
将无序数组构造成一个大顶堆。我们从最后一个非叶子节点开始，从下往上、从右往左进行调整（Heapify），确保每个子树都满足大顶堆性质。
- 为什么要从最后一个非叶子节点开始？ 因为叶子节点本身已经满足堆性质，不需要调整。
排序 (Sorting)：
- 将堆顶元素（最大值）与数组末尾元素交换。此时，末尾元素就是最大值，将其从堆的范围内“移除”（逻辑上忽略）。
- 将剩余的 $n-1$ 个元素重新调整为大顶堆（只需对根节点进行 Heapify）。
- 重复上述步骤，直到堆的大小变为 1。

2. C++ 代码实现

作为计算机专业的学生，理解 C++ 的底层实现非常重要。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 维护堆性质的函数 (Heapify)
// n: 堆的有效大小
// i: 当前需要调整的节点索引
void heapify(vector<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) {
        swap(arr[i], arr[largest]);

        // 递归地调整受影响的子树
        heapify(arr, n, largest);
    }
}

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

    // 1. 建堆 (Build Max Heap)
    // 从最后一个非叶子节点 (n/2 - 1) 开始调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大的元素 (arr[0]) 移到数组末尾 (arr[i])
        swap(arr[0], arr[i]);

        // 对剩余的 i 个元素，重新调整根节点以恢复大顶堆
        heapify(arr, i, 0);
    }
}

int main() {
    vector<int> data = {12, 11, 13, 5, 6, 7};
    heapSort(data);

    cout << "Sorted array is \n";
    for (int i : data)
        cout << i << " ";
    cout << endl;
    return 0;
}
`

3. 复杂度分析

指标	描述
时间复杂度	$O(n \log n)$ (无论是最好、最坏还是平均情况)
空间复杂度	$O(1)$ (原地排序，不需要额外辅助数组)
稳定性	不稳定 (Unstable) (交换堆顶和末尾元素时可能会打乱相同元素的相对位置)

注意：虽然建堆的时间复杂度是 $O(n)$，但排序过程需要遍历 $n$ 次，每次调整耗时 $O(\log n)$，所以总耗时是 $O(n \log n)$。

4. 注意事项与应用场景

下标计算：注意你的数组是 0 开始还是 1 开始。如果是 0 开始（如 C++/Java/Python），左孩子是 $2i+1$；如果是 1 开始，左孩子是 $2i$。
Top K 问题：堆排序最经典的应用不是全排序，而是求数组中第 K 大或前 K 大的元素。
- 求 Top K 最大：维护一个大小为 K 的小顶堆。
- 求 Top K 最小：维护一个大小为 K 的大顶堆。
- 这样可以将复杂度降低到 $O(n \log k)$。
缓存命中率：虽然堆排序的时间复杂度与快速排序、归并排序一样都是 $O(n \log n)$，但在实际运行中，堆排序通常比快速排序慢。因为堆排序的索引跳转是不连续的（跳跃访问数组），对 CPU 缓存（Cache）不友好。

5. LeetCode 精选例题

以下题目建议按照顺序练习，能够涵盖堆排序的核心思想和变体。

5.1 基础练习

912. 排序数组 (Sort an Array)
- 描述：给你一个整数数组 nums，请你将该数组升序排列。
- 思路：这是裸题，直接手写一遍 Heap Sort 通过此题，不要使用库函数，考察代码实现能力。

5.2 进阶应用 (Top K)

215. 数组中的第K个最大元素 (Kth Largest Element in an Array)
- 描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
- 思路：
  1. 全排序：堆排序后取下标。
  2. 优化：建立大顶堆，删除 $k-1$ 次堆顶，当前的堆顶即为答案。或者维护一个大小为 $k$ 的小顶堆。

5.3 堆的合并

23. 合并 K 个升序链表 (Merge k Sorted Lists)
- 描述：给你 $k$ 个链表的头节点，将它们合并成一个升序链表。
- 思路：虽然是链表，但核心思想是优先队列（最小堆）。将 $k$ 个链表的头节点放入小顶堆，每次弹出最小的节点接到结果链表后，并将该节点的下一个节点入堆。

5.4 频次统计

347. 前 K 个高频元素 (Top K Frequent Elements)
- 描述：给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。
- 思路：先用 Hash Map 统计频率，然后将 (频率, 元素) 对放入大小为 $k$ 的小顶堆中。如果新元素的频率大于堆顶，则弹出堆顶并插入新元素。