堆排序 - NOI提高级教程

📖 算法原理：建堆与循环置换

堆排序是利用完全二叉堆（Binary Heap）进行的选择排序。它包含两个核心阶段：

阶段 1：构建初始大根堆 (Build Max Heap)：自底向上，从最后一个非叶子节点开始，对每一个父节点执行 siftDown 向下调整，使其均大于或等于孩子节点。
阶段 2：堆顶置换与调整 (Heap Sort Loop)：循环 $N-1$ 次，每次将最大值的堆顶元素与当前的堆尾元素交换，将其在堆的结构上剪除（标记为有序归位），并对新的堆顶运行 siftDown 向下调整。

🧠 NOI 必考时空复杂度断言

时间复杂度：建堆开销为线性时间 $O(N)$；排序循环共 $N-1$ 次，每次最大调整深度为 $\log N$。总时间复杂度严格稳定在 $O(N \log N)$，不受输入排序状态影响。
空间复杂度：所有排序操作都在原数组内部通过交换完成，辅助空间复杂度为 $O(1)$（原地排序）。
稳定性：在大根堆的向下调整中，同值元素的相对物理位置可能会被跨度跳跃式互换，故属于 不稳定排序。

演示速度：

点击"自动播放"或"单步演练"观察大根堆构建与堆顶置换排序过程

// 堆排序核心代码
void siftDown(int a[], int i, int n) {
    int parent = i;
    int child = 2 * parent + 1; // 左孩子索引
    while (child < n) {
        // 若有右孩子且右孩子更大，则指向右孩子
        if (child + 1 < n && a[child] < a[child + 1]) child++;
        // 父节点已大于等于最大子节点，则调整完毕
        if (a[parent] >= a[child]) break;
        swap(a[parent], a[child]); // 违背堆序，执行对调
        parent = child;
        child = 2 * parent + 1;
    }
}

void heapSort(int a[], int n) {
    // 1. 自底向上建堆
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
    // 2. 堆顶置换并调整
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]); // 堆顶最大值与堆尾交换
        siftDown(a, 0, i); // 重新向下调整维护堆
    }
}

📋 算法执行步骤历史