题目描述
① 建大顶堆(堆顶=最大)。② 把堆顶和末尾交换(最大值归位)，堆缩小一个，再下沉修复堆顶。重复直到堆空。
输入 = [4, 10, 3, 5, 1]
输出 = [1, 3, 4, 5, 10]
思路解析
从最后一个非叶子节点开始逐个"下沉"，建成大顶堆（堆顶 = 最大）。然后每轮：堆顶和当前末尾交换 → 末尾归位 → 堆长度减一 → 新堆顶下沉到合适位置。
建大顶堆：先把原数组 [4,10,3,5,1] 调整成大顶堆 [10,5,3,4,1]：堆顶 10 是最大值（每个父都 ≥ 它的孩子）。
堆顶 10 ↔ 末尾 1：把堆顶 10 和末尾交换：10 归位到最右。堆缩小到前 4 个，但堆顶变成了小的 1，需要下沉修复。
下沉① · 1 和较大孩子 5 交换：修复开始：堆顶 1 的两个孩子是 5(下标1)、3(下标2)，选较大的 5，1 比 5 小 → 交换，1 下沉一层到下标 1。
下沉② · 1 再和孩子 4 交换：1 在下标 1，它的孩子是 4(下标3)，1 比 4 小 → 再交换，1 沉到下标 3（已无孩子，停）。堆修复完成，新堆顶 = 次大值 5。
5 ↔ 末尾 · 5 归位：再把堆顶 5 换到当前末尾（下标 3），5 归位。堆缩到前 3 个，堆顶 1 继续下沉修复。
重复直到堆空：重复"取顶→换末尾→下沉"，每轮固定一个最大值到右边。最终 [1,3,4,5,10] 有序。
堆排是"选择排序的提速版"：选择排序每趟 O(n) 找最大，堆排用堆 O(log n) 取最大。堆这个结构（优先队列）在 Top-K、合并K路、Dijkstra 里无处不在。
参考代码（Python）
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
7for i in range(n//2-1, -1, -1): sift_down(a, i, n) # 建堆
8for end in range(n-1, 0, -1):
9 a[0], a[end] = a[end], a[0]; sift_down(a, 0, end) # 取顶+修复复杂度分析
- 时间复杂度：O(n log n) —— 建堆 O(n) + n 次下沉
- 空间复杂度：O(1) —— 原地，无额外数组
套路模板
记住骨架：孩子 2i+1/2i+2、选较大孩子、父不够大就交换下沉。直接用语言自带的优先队列（heapq）能省去手写。
Python
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 # 交换继续下沉易错点
- ❌ 孩子下标记成 2i → ✅ 左孩子 2i+1、右孩子 2i+2（下标从 0 开始时的固定公式）
- ❌ 取顶后不缩短堆长 → ✅ sift_down 传入递减的 end（已归位的末尾不能再参与堆调整）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。