题目描述
① 建大顶堆（堆顶＝最大）。② 把堆顶和末尾交换（最大值归位），堆缩小一个，再下沉修复新堆顶。重复直到堆空。
思路解析
选择排序每趟都得把未排序区从头扫到尾才知道谁最大，找一次最大值要 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 里无处不在，比堆排本身用得还多。
参考代码（Python）
1def sift_down(a, i, n): # 让下标 i 下沉到合适位置
2 while 2*i + 1 < n: # 还有左孩子才继续
3 c = 2*i + 1 # 左孩子下标
4 if c + 1 < n and a[c+1] > a[c]: c += 1 # 选较大孩子
5 if a[i] >= a[c]: break # 父已不小于孩子，停
6 a[i], a[c] = a[c], a[i]; i = c # 交换后继续往下沉
7n = len(a)
8for i in range(n//2 - 1, -1, -1): sift_down(a, i, n) # 建堆
9for end in range(n - 1, 0, -1):
10 a[0], a[end] = a[end], a[0]; sift_down(a, 0, end) # 取顶+修复复杂度分析
- 时间复杂度：O(n log n) —— 建堆 O(n)，之后 n 次取顶各做一次 O(log n) 下沉
- 空间复杂度：O(1) —— 只在原数组上交换，不开额外数组
套路模板
记住骨架：左右孩子 2i+1 / 2i+2、选较大孩子、父不够大就交换下沉。实战直接用语言自带的优先队列（Python 的 heapq）能省去手写。
1def sift_down(a, i, n):
2 while 2*i + 1 < n:
3 c = 2*i + 1
4 if c + 1 < n and a[c+1] > a[c]: c += 1 # 较大孩子
5 if a[i] >= a[c]: break # 已满足堆性质就停
6 a[i], a[c] = a[c], a[i]; i = c # 交换继续下沉易错点
- 错误写法：左孩子下标写成 2*i → 正确写法：左孩子 2*i+1、右孩子 2*i+2（下标从 0 开始时父子关系的固定公式，写成 2*i 会把自己当孩子，整棵堆乱掉）
- 错误写法：建堆从下标 0 正向 sift_down → 正确写法：从 n//2−1 倒着往 0 做（下沉要求孩子子树已经是堆；只有自底向上（叶子已天然是堆）才满足这个前提）
- 错误写法：取顶后不缩短堆长 → 正确写法：sift_down 传入递减的 end 作为堆长（已归位到末尾的最大值不能再参与下沉，否则会被换回堆里）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。