🌲 堆排序 (Heap Sort)

归档: #Algorithm #Sorting #Advanced

核心心法: "特权阶级" —— 维护一个最大堆，老大的位置永远在堆顶。

🧠 核心思想

利用 完全二叉树 的性质。

1. 建堆 (Build Heap)：把乱序数组调整成一个大顶堆（父节点 > 子节点）。
2. 交换 (Swap)：把堆顶（最大值）和数组末尾元素交换 -> 最大值锁定。
3. 下沉 (Sink/Heapify)：把换到堆顶的小元素“沉”下去，恢复堆的性质。

🎨 图解演示

点击“开始排序”演示堆化过程

4

0

10

1

3

2

5

3

1

4

2

5

8

6

父节点 比较中子节点 已锁定

💻 代码实现 (C++)

class Solution {
public:
    void heapSort(vector<int>& nums) {
        int n = nums.size();
        // 1. 建堆：从最后一个非叶子节点开始 sink
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(nums, n, i);
            
        // 2. 排序：把堆顶换到最后，然后缩小堆范围
        for (int i = n - 1; i > 0; i--) {
            swap(nums[0], nums[i]); // 最大值归位
            heapify(nums, i, 0);    // 剩下的继续堆化
        }
    }

    // 下沉函数：维护堆性质的核心
    void heapify(vector<int>& arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        
        if (largest != i) {
            swap(arr[i], arr[largest]);
            heapify(arr, n, largest); // 递归下沉
        }
    }
};

📊 复杂度分析

维度	数值	说明
时间 (平均)		建堆 , 排序
空间		原地操作，不需要额外数组
稳定性	❌ 不稳定	堆顶交换破坏了顺序

💡 适用场景

• 空间极度受限：不能用递归（防爆栈），不能用额外数组（如嵌入式设备），堆排是唯一的 选择。

• Top K 问题：找 10 亿个数里最大的 10 个，不需要全排序，只需维护大小为 10 的堆。