堆排序（Heap Sort）

算法原理

堆排序（Heap Sort）把数组当成一棵完全二叉树来用：下标 i 的节点，左孩子是 2i+1、右孩子是 2i+2、父亲是 ⌊(i-1)/2⌋——不需要任何指针，树就住在数组的下标算术里。大顶堆在这棵树上加一条秩序：每个父节点都不小于它的孩子，于是全数组最大的值必然坐在堆顶 a[0]。排序 = 反复"摘顶"：把堆顶与堆尾交换，让最大值落到它的终位，堆规模缩一格，再把新上来的堆顶下沉到它该待的位置，恢复堆序。

本动画在 8 个元素上演示完整两幕：先 Floyd 自底向上建堆（从最后一个非叶节点倒序下沉，O(n)），再 7 轮摘顶提取（每轮顶尾⇄ + 下沉修复）。上树下行两个视角同拍镜像同一次交换——树上看是"父子上交换"，数组里看是"两个下标互换"。

节拍（动画严格按此演示）：

建堆（Floyd）：从最后一个非叶节点 i = ⌊(n-2)/2⌋ 倒序到 0，逐节点下沉；
下沉一步：在两个孩子中取较大者与父比较——父大则下沉结束；子大则父子换位，活动值落到孩子位置继续下沉，直到叶子；
摘顶：堆顶（当前最大值）与堆尾 a[h] 交换——堆顶一步长滑到终位，行区亮绿✓，树区该节点转空巢，堆规模减一；
修复：被换到堆顶的前堆尾值下沉到合适位置，堆序恢复；
重复摘顶直到堆只剩一格——整个数组有序。

动画怎么看

橙色卡：正在下沉的活动值，全屏唯一、两区随飞——建堆期的种子值、提取期被换起的堆尾值；
金线：比较拍点亮的父—较大子活跃边，"孩子二选一取大"的判定瞬间；子节点卡描边同亮；
深绿卡（带 ✓）：已归位的终位值，只出现在数组行，终身不褪；
空巢（淡描边框）：已出堆的树节点——值离开堆、封存进数组行后，树轮廓保持完整，灰色 a[i] 留守；
行光晕：还住在堆里的数组前缀 [0..h]，随每轮摘顶同步收缩；
终幕：完成拍排序完成的值以绿色亮回树区——按树形从上到下、从左到右读，恰好就是升序。

上树下行各有一排常驻小字（节点上方 a[i]、卡片下方 i），这就是"堆=数组"的算术证据：节点 3 的孩子是 2×3+1=7——末层那个唯一的左孩子。

复杂度分析

项目	复杂度	说明
时间	O(n log n)	建堆 O(n)（Floyd，多数节点沉得浅）+ n-1 轮摘顶，每轮下沉至多 O(log n)；最坏、平均、最好都是 O(n log n)
空间	O(1)	原地交换，只用常数个变量（本动画的树只是下标算术，不占额外空间）
稳定性	不稳定	摘顶会把堆尾值换到根再沉下去，可能跨越等值元素、打乱原始次序

C++ 参考代码

#include <iostream>
#include <vector>
using namespace std;

// 下沉：在 heap[0..=h] 范围内，把 a[i] 沉到该待的位置
void siftDown(vector<int>& a, int i, int h) {
    while (true) {
        int child = 2 * i + 1;               // 左孩子
        if (child > h) break;                // 已是叶子
        if (child + 1 <= h && a[child + 1] > a[child])
            child++;                         // 孩子二选一取大
        if (a[i] >= a[child]) break;         // 父不小于大子：堆序恢复
        swap(a[i], a[child]);                // 换位，继续向下
        i = child;
    }
}

void heapSort(vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; i--)     // Floyd 自底向上建大顶堆
        siftDown(a, i, n - 1);
    for (int h = n - 1; h > 0; h--) {
        swap(a[0], a[h]);                    // 摘顶：最大值换到终位
        siftDown(a, 0, h - 1);               // 新堆顶下沉修复
    }
}

int main() {
    vector<int> a = {38, 17, 52, 9, 41, 25, 60, 13};
    heapSort(a);
    for (int x : a) cout << x << ' ';        // 输出：9 13 17 25 38 41 52 60
    cout << endl;
    return 0;
}

什么时候用堆排序

堆排序是「只要最值、且要得反复」这类问题的底座：Top-K、优先队列、多路归并的取最小、定时器的最近到期任务——全是堆（或它的指针化形态）在撑。作为排序，它最坏也只有 O(n log n) 且 O(1) 空间，是快排（最坏 O(n²)）、归并（O(n) 辅助数组）之外的第三种保底选择；代价是缓存不友好（下沉跳跃访问）与不稳定，实践中常作为** introsort 的兜底**与 std::push_heap / pop_heap 的内核。写法上最易错的是下沉里「孩子二选一取大」与建堆起点 n/2-1 倒序——本动画的金线判定拍与建堆序号正是这两处的可视化。