堆排序的原理是什么？它和快排、归并相比有什么优劣？

简化版

堆排序两步:①把数组原地建成大顶堆(升序排序用大顶堆),O(n);②反复把堆顶(最大值)和末尾交换、堆规模减 1、对新堆顶下沉,把最大值依次甩到数组尾部,得到升序。时间最好=平均=最坏都是 O(n log n)、空间原地 O(1)、不稳定。优势是「最坏有保证 + 省内存」,但缓存不友好(跳跃访问),实际常比快排慢。

详细版

void heapSort(int[] a) {
    int n = a.length;
    for (int i = n/2 - 1; i >= 0; i--) siftDown(a, i, n); // 1. 建大顶堆 O(n)
    for (int end = n - 1; end > 0; end--) {
        swap(a, 0, end);            // 2. 堆顶(最大)换到末尾（就位）
        siftDown(a, 0, end);        // 对前 end 个元素重新下沉，堆缩小 1
    }
}
void siftDown(int[] a, int i, int size) {
    while (true) {
        int l = 2*i+1, r = 2*i+2, largest = i;
        if (l < size && a[l] > a[largest]) largest = l;
        if (r < size && a[r] > a[largest]) largest = r; // 找较大的孩子
        if (largest == i) break;
        swap(a, i, largest); i = largest;
    }
}

升序用大顶堆:堆顶是最大值,每次甩到末尾,从后往前排好。
排序区间 [0, end) 逐步缩小,[end, n) 是已排好的部分。

完整版教学

一、堆排序 = 用堆加速的选择排序

理解堆排序,可以把它看成选择排序的高效版。选择排序每轮要 O(n) 地扫一遍找最大值,n 轮共 O(n²)。堆排序用大顶堆这个数据结构,把「找当前最大值」从 O(n) 降到 O(log n)(取堆顶 + 下沉),于是总复杂度降到 O(n log n)。所以堆排序的本质是「借助堆结构,快速地反复取出最大值放到末尾」。

二、两个阶段:建堆 + 排序

阶段一:建堆(O(n))。把无序数组原地整理成大顶堆——从最后一个非叶子节点 n/2-1 开始,倒序对每个节点做下沉。自底向上建堆是 O(n)(大部分节点在底层、下沉高度小)。

阶段二:反复取最大(O(n log n))。堆顶是最大值,把它和数组当前末尾交换(最大值就位到末尾),然后堆规模减 1、对换上来的新堆顶下沉,恢复堆序。重复 n-1 次,最大值、次大值……依次填到数组尾部,从后往前排好,整体升序。

三、为什么升序要用大顶堆(易错点)

这点常搞反:升序排序用大顶堆。因为大顶堆的堆顶是最大值,每次把它换到当前未排序区的末尾,最大的先放最后、次大的放倒数第二……从后往前填,最终得到从小到大的升序。反过来,降序排序用小顶堆。记住:升序大顶堆、降序小顶堆(和直觉相反)。

四、为什么最坏也是 O(n log n)

堆排序的建堆是 O(n),之后 n-1 次「取堆顶 + 下沉」,每次下沉最多 O(log n),所以是 O(n log n)。关键是:下沉的代价只和堆高有关,而堆(完全二叉树)的高度恒为 log n,与数据内容无关。所以堆排序没有最坏退化——最好、平均、最坏全是 O(n log n)。这点和归并一样稳,而快排最坏会到 O(n²)。

五、为什么原地 O(1) 空间

堆排序直接在原数组上操作:把数组本身当成堆(用下标 2i+1、2i+2 表示父子关系),建堆和下沉都是原地交换,不需要任何辅助数组。所以空间是 O(1)(迭代下沉,无递归栈)。这是它相对归并(O(n) 空间)的优势——又省内存、又有最坏保证。

六、为什么堆排序不稳定

堆排序不稳定。在建堆和「堆顶换末尾」的过程中,会发生远距离交换(堆顶和末尾、父和子跨越很多元素),这些交换可能把相等元素的相对顺序打乱。所以堆排序和快排、选择一样不稳定。

七、和快排、归并的对比(重点)

三大 O(n log n) 排序的取舍:

	快速排序	归并排序	堆排序
平均时间	O(n log n)	O(n log n)	O(n log n)
最坏时间	O(n²)	O(n log n)	O(n log n)
空间	O(log n)	O(n)	O(1)
稳定	❌	✅	❌
实际速度	最快	较快	较慢

堆排序 vs 快排:堆排最坏有保证(O(n log n))、省内存(O(1)),但缓存不友好——堆的父子访问(下标 2i)在内存里跳来跳去,缓存命中率低;快排是顺序扫描连续内存,缓存友好。所以实际中堆排序常比快排慢,尽管复杂度相同。
堆排序 vs 归并:都最坏 O(n log n),但堆排原地 O(1)、归并要 O(n) 空间;不过归并稳定、堆排不稳定。
定位:堆排序适合「要保证最坏性能,又要省内存」的场景,也常作为快排的兜底(introsort:快排递归过深时切堆排,把最坏拉回 O(n log n))。

八、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：[0,heapSize) 始终是大顶堆，[heapSize,n) 是已归位的升序后缀。

对应的状态推进是：建堆后反复交换堆顶与堆尾，缩小 heapSize，再从根向下调整。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。自底向上建堆 O(n)，n-1 次下沉使总时间 O(n log n)。

带数字走一遍：[4,10,3,5,1] 建堆为 [10,5,3,4,1]，先把 10 放到末尾。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	需要原地且要求最坏 O(n log n) 时适用，但缓存局部性不如快排
时间复杂度	最好/平均/最坏 O(n log n)
额外空间	迭代下沉 O(1)
关键边界	最后非叶子是 floor(n/2)-1；下沉先选更大的孩子并检查下标
替代方案	稳定排序选归并；频繁取极值直接使用优先队列

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

九、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“需要原地且要求最坏 O(n log n) 时适用，但缓存局部性不如快排”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写最好/平均/最坏 O(n log n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“自底向上建堆 O(n)，n-1 次下沉使总时间 O(n log n)”。
误区：重复值和边界值不会改变代码。 最后非叶子是 floor(n/2)-1；下沉先选更大的孩子并检查下标。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“[0,heapSize) 始终是大顶堆，[heapSize,n) 是已归位的升序后缀”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[4,10,3,5,1] 建堆为 [10,5,3,4,1]，先把 10 放到末尾”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“稳定排序选归并；频繁取极值直接使用优先队列”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

十、加强记忆

堆排序两步:原地建大顶堆(O(n))→ 反复「堆顶换末尾、堆缩小、新堆顶下沉」,把最大值依次甩到尾部(升序)。最好=平均=最坏都 O(n log n)(堆高恒 log n、无退化)、原地 O(1) 空间、不稳定。记「升序大顶堆、降序小顶堆」。相比快排:最坏有保证+省内存,但缓存差、实际较慢;常作为 introsort 的兜底。

简化版

详细版