上一页说堆排序要靠「堆」这个结构。你可能已经见过优先级队列：每次取出的总是最优先的那个。堆正是它的底层实现——关键在两条规则：谁在上、怎么摆。

上一页我们建好了一个大顶堆：堆顶永远是最大值。现在换个角度想——每一轮把最大值「选」出来放到末尾，这不就是选择排序吗？堆只是给了我们一个找最大值的高效结构。

从无序数组出发，先花一次代价把数组调成大顶堆，再反复交换堆顶与末位并缩堆，直到全部有序。

上一页我们知道堆排序就是反复摘顶。可为什么要先费力建堆？回忆选择排序：每轮线性扫描找最大值要 O(n)，重复 n 轮就是 O(n²)。堆正是为了解决「找最值太慢」这个瓶颈。

前面几页我们说了：堆排序=建堆+反复摘顶。你可能注意到，摘出来的元素往哪放了？答案是和堆尾交换——整个排序就在原数组里腾挪，几乎不借外部空间，这就是就地排序。

把数组横着看：左段仍是堆，右段是已排好的最大值，虚线边界随每轮交换左移一格。

摘顶循环每轮三步：交换、下滤、收缩，缺一不可。

上一页的循环把最大值换到数组尾部——「最大」从哪来？答案取决于堆型：升序要每次摘出最大，所以用大顶堆。如果误用小顶堆，摘出的是最小值，放到尾部就成了降序，边界必须辨析清楚。

上一页定了要用大顶堆，但堆不是天生的——拿到一个乱序数组，得先把它「堆化」。怎么建这个堆？有两条路线：一个个往里插，或者从下往上整批调整。代价差别大得惊人。

Floyd 建堆从最后一个内部节点起逆序下滤，把零散子树合并成整体堆。

一段可运行的下滤代码：父亲不断与较大的孩子交换，直到恢复堆序。

四个关键点：没有孩子就停、选较大的孩子比较、父亲够大就提前终止、否则交换并继续下沉——每一处都决定下滤是否正确。

Floyd 建堆 + 反复交换下滤，完整的就地堆排序落地。

L4-5 是 Floyd 建堆：从最后一个非叶节点倒序下滤；L9-11 摘顶循环：交换后堆区间收缩，end 同时是已排序区间的左边界。

前面已完整实现堆排序：Floyd 建堆加上反复摘顶。现在把账算清楚——为什么整体是 O(nlogn)？这个算法省下了什么，又付出了什么代价？

以数组 [4, 6, 8, 5, 9] 为例，从最后一个非叶结点出发逐个下滤，把乱序数组建成大顶堆。

每轮三连：交换、下滤、收缩，最大值逐个落到尾部。

给定堆快照，判断下一轮交换与下滤的结果

• ✓两阶段缺一不可：Floyd 建堆 O(n)，摘顶 O(n log n)
• ✓大顶堆配升序：摘顶后最大值沉到尾部
• ✓就地排序的本质：堆区间不断收缩，无需辅助数组
• ✓交换后必须下滤恢复堆序，再收缩边界
• ✓不稳定：长距离交换会打乱相等元素的相对次序

三个问题先自己想五分钟，再看参考答案。