堆排序借助最大堆或最小堆。建立堆后，每次把堆顶元素放到数组尾部，调整堆，再继续做。

Ph1zの理解： 堆排序就像一个选拔赛——堆顶永远是当前最强的人。每轮把最强的人"淘汰"到最终位置，然后重新组织剩下的比赛（siftDown 恢复堆性质）。重复 $n$ 轮，选拔完成。

代码

void heapSort(int a[], int n) {
    makeHeap(a, n);               // 建大根堆
    for (int i = n - 1; i > 0; --i) {
        std::swap(a[0], a[i]);
        siftDown(a, 0, i);       // 维护堆性质
    }
}

正确性证明

堆的核心性质：堆顶一定是当前最大值（大根堆）。

• 建堆后，堆顶元素是当前最大元素。
• 把堆顶与末尾交换后，最大元素已落到最终位置；剩余前部仍构成堆。
• 重新执行 siftDown，恢复堆性质。
• 重复这一过程，最终所有元素从大到小依次被放到最终位置，因此数组整体有序。 ✓

Ph1zの理解： 堆是一种"部分有序"的结构——只保证父节点 ≥ 子节点，不保证左右子节点的大小关系。但这已经够了：我们只需要每轮知道谁是最大值，不需要完全排序。

复杂度分析

步骤	复杂度	说明
建堆	$O(n)$	从底向上 siftDown，看似 $O(n\log n)$ 实则 $O(n)$
取堆顶 + 调整	$(n-1)\times O(\log n)$	每次 siftDown 最多走树高 $\log n$

所以：

$$T(n)=O(n)+O(n\log n)=O(n\log n).$$

最好、平均、最坏都为 $O(n\log n)$——堆排序和归并排序一样，不挑数据，不退化。

建堆为什么是 $O(n)$ 而不是 $O(n\log n)$？ 直觉上，$n$ 个元素每个 siftDown 最多 $\log n$，应该是 $O(n\log n)$。但实际上，大部分节点在树的下层，siftDown 路径很短。精确计算：$\sum _{h=0}^{\log n}\frac{n}{2^{h+1}}\cdot O(h)=O(n)$。叶子节点（占一半）根本不用动！

空间复杂度： $O(1)$（原地排序）。

稳定性： 不稳定。因为堆顶与末尾交换时，等值元素可能发生位置变化。

堆排序的独特价值： 它是唯一一个既原地（$O(1)$ 额外空间）又最坏 $O(n\log n)$ 的比较排序。归并排序需要 $O(n)$ 额外空间，快排最坏 $O(n^2)$——堆排序两头都占了。但它的缓存不友好（数据访问跳跃大），所以实测通常比快排慢。