困难排序 · 堆排
堆排序 图解题解
这道题到底在问什么
① 建大顶堆（堆顶＝最大）。② 把堆顶和末尾交换（最大值归位），堆缩小一个，再下沉修复新堆顶。重复直到堆空。
- 输入
- [4, 1, 3, 2, 6, 5]
- 输出
- [1, 2, 3, 4, 5, 6]
最优解：一步一步想明白
- 3选择排序每趟都得把未排序区从头扫到尾才知道谁最大，找一次最大值要 O(n)，n 趟就是 O(n²)。堆排的提速点就在这：用「堆」这个结构，把「找最大」从 O(n) 压到 O(log n)。
- 4只要维持「父不小于子」这个性质，堆顶（下标 0）就一定是全局最大。取走堆顶后堆性质被破坏，靠一次下沉（把新堆顶和较大的孩子换、一路沉到合适位置）就能 O(log n) 修复——这是堆排成立的根。
- 5i=2 孩子 5建堆从最后一个非叶子节点 n//2−1=2 往前做。下标 2 的值 3，唯一孩子是下标 5 的 5：孩子比父大，交换，3 下沉到下标 5。
- 6i=1 选较大孩子 6换下标 1 的值 1：它的孩子是下标 3 的 2 和下标 4 的 6，选较大的孩子 6。1 比 6 小，交换，1 沉到下标 4。
- 7i=0 选较大孩子 6最后下沉根 4：孩子是下标 1 的 6 和下标 2 的 5，选较大的 6。4 比 6 小，交换，4 沉到下标 1。
- 84 不小于 2 → 停4 沉到下标 1 后，它的孩子是下标 3 的 2，4 不小于 2，已满足堆性质，停止下沉——这就是下沉的负例分支：父够大就不再往下换。大顶堆建好：堆顶 6 是最大值。
- 9swap(0,5) · 6 归位把堆顶 6 和当前末尾下标 5 交换：6 归位到最右。堆缩小到前 5 个，但堆顶变成了小的 3，需要下沉修复。
- 10sift_down(0, n=5)在前 5 个里修复堆顶 3：孩子是下标 1 的 4 和下标 2 的 5，选较大的 5。3 比 5 小，交换，3 沉到下标 2（已无孩子，停）。新堆顶＝次大值 5。
- 11swap(0,4) · 5 归位再把堆顶 5 换到当前末尾下标 4：5 归位。堆缩到前 4 个，堆顶又变成小的 3，继续下沉修复。
- 12done重复「取顶 → 换末尾 → 缩短堆长 → 下沉修复」，每轮固定一个当前最大值到右边。最终 [1,2,3,4,5,6] 全部归位。
- 15堆排是「选择排序的提速版」：选择排序每趟 O(n) 找最大，堆排用堆 O(log n) 取最大。堆（优先队列）这个结构在 Top-K、合并 K 路、Dijkstra 里无处不在，比堆排本身用得还多。
⚠️ 容易写错的地方
✗ 错：左孩子下标写成 2*i
✓ 对：左孩子 2*i+1、右孩子 2*i+2
下标从 0 开始时父子关系的固定公式，写成 2*i 会把自己当孩子，整棵堆乱掉
✗ 错：建堆从下标 0 正向 sift_down
✓ 对：从 n//2−1 倒着往 0 做
下沉要求孩子子树已经是堆；只有自底向上（叶子已天然是堆）才满足这个前提
✗ 错：取顶后不缩短堆长
✓ 对：sift_down 传入递减的 end 作为堆长
已归位到末尾的最大值不能再参与下沉，否则会被换回堆里
完整代码（Python）
Python
def sift_down(a, i, n): # 让下标 i 下沉到合适位置
while 2*i + 1 < n: # 还有左孩子才继续
c = 2*i + 1 # 左孩子下标
if c + 1 < n and a[c+1] > a[c]: c += 1 # 选较大孩子
if a[i] >= a[c]: break # 父已不小于孩子，停
a[i], a[c] = a[c], a[i]; i = c # 交换后继续往下沉
n = len(a)
for i in range(n//2 - 1, -1, -1): sift_down(a, i, n) # 建堆
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]; sift_down(a, 0, end) # 取顶+修复套路模板 · 下沉建堆（背下来）
def sift_down(a, i, n):
while 2*i + 1 < n:
c = 2*i + 1
if c + 1 < n and a[c+1] > a[c]: c += 1 # 较大孩子
if a[i] >= a[c]: break # 已满足堆性质就停
a[i], a[c] = a[c], a[i]; i = c # 交换继续下沉复杂度
时间复杂度
O(n log n)
建堆 O(n)，之后 n 次取顶各做一次 O(log n) 下沉
空间复杂度
O(1)
只在原数组上交换，不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 堆排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「堆排」，换最直接的暴力解会差在哪？+
堆排抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。