堆排序

选择排序每趟都得把未排序区从头扫到尾才知道谁最大，找一次最大值要 O(n)，n 趟就是 O(n²)。堆排的提速点就在这：用「堆」这个结构，把「找最大」从 O(n) 压到 O(log n)。

只要维持「父不小于子」这个性质，堆顶（下标 0）就一定是全局最大。取走堆顶后堆性质被破坏，靠一次下沉（把新堆顶和较大的孩子换、一路沉到合适位置）就能 O(log n) 修复——这是堆排成立的根。

建堆 · 下沉下标 2（值 3）：建堆从最后一个非叶子节点 n//2−1=2 往前做。下标 2 的值 3，唯一孩子是下标 5 的 5：孩子比父大，交换，3 下沉到下标 5。

建堆 · 下沉下标 1（值 1）：换下标 1 的值 1：它的孩子是下标 3 的 2 和下标 4 的 6，选较大的孩子 6。1 比 6 小，交换，1 沉到下标 4。

建堆 · 下沉下标 0（值 4）：最后下沉根 4：孩子是下标 1 的 6 和下标 2 的 5，选较大的 6。4 比 6 小，交换，4 沉到下标 1。

建堆 · 4 不小于孩子 → 停（负例）：4 沉到下标 1 后，它的孩子是下标 3 的 2，4 不小于 2，已满足堆性质，停止下沉——这就是下沉的负例分支：父够大就不再往下换。大顶堆建好：堆顶 6 是最大值。

取顶① · 堆顶 6 换到末尾：把堆顶 6 和当前末尾下标 5 交换：6 归位到最右。堆缩小到前 5 个，但堆顶变成了小的 3，需要下沉修复。

修复① · 3 下沉，和较大孩子 5 换：在前 5 个里修复堆顶 3：孩子是下标 1 的 4 和下标 2 的 5，选较大的 5。3 比 5 小，交换，3 沉到下标 2（已无孩子，停）。新堆顶＝次大值 5。

取顶② · 堆顶 5 换到下标 4：再把堆顶 5 换到当前末尾下标 4：5 归位。堆缩到前 4 个，堆顶又变成小的 3，继续下沉修复。

重复直到堆空 · 全部有序：重复「取顶 → 换末尾 → 缩短堆长 → 下沉修复」，每轮固定一个当前最大值到右边。最终 [1,2,3,4,5,6] 全部归位。

堆排是「选择排序的提速版」：选择排序每趟 O(n) 找最大，堆排用堆 O(log n) 取最大。堆（优先队列）这个结构在 Top-K、合并 K 路、Dijkstra 里无处不在，比堆排本身用得还多。