题目描述
思路解析动画文字版
记住一句话：下沉(sift down) = 父亲若比孩子小，就和较大的孩子换位置，一路往下，直到坐稳。建堆和取顶后修复，用的都是这一个动作。
取顶 = 堆顶换到末尾(最大值归位) → 堆缩小一格 → 新堆顶下沉修复。每轮锁定一个最大值在尾部，绿色就是已排好的部分。
第一阶段：建大顶堆。从最后一个「有孩子的节点」开始，逐个向前做下沉，把每棵子树都整理成父亲最大。
处理子树根 下标 2：看父亲(橙)下标 2=3 和它的孩子下标 5=5：较大的孩子是下标 5=5，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 2 处坐着更大的 5。被换下去的 3 继续往下沉，看它还压不压得住孙辈。
处理子树根 下标 2：看父亲(橙)下标 5=3 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
处理子树根 下标 1：看父亲(橙)下标 1=1 和它的孩子下标 3=2、下标 4=6：较大的孩子是下标 4=6，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 1 处坐着更大的 6。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
处理子树根 下标 1：看父亲(橙)下标 4=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
处理子树根 下标 0：看父亲(橙)下标 0=4 和它的孩子下标 1=6、下标 2=5：较大的孩子是下标 1=6，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 6。被换下去的 4 继续往下沉，看它还压不压得住孙辈。
处理子树根 下标 0：看父亲(橙)下标 1=4 和它的孩子下标 3=2、下标 4=1：父亲已经是其中最大，不用动，下沉结束。
大顶堆建好了：堆顶下标 0=6 就是整个数组的最大值。接下来进入取顶阶段，把它换到末尾归位。
取顶第 1 轮：把堆顶 6(当前最大)和堆的最后一格 下标 5=3 交换，最大值即将归位到尾部。
最大值 6 归位到下标 5，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…4。
新堆顶下沉：看父亲(橙)下标 0=3 和它的孩子下标 1=4、下标 2=5：较大的孩子是下标 2=5，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 5。被换下去的 3 继续往下沉，看它还压不压得住孙辈。
新堆顶下沉：看父亲(橙)下标 2=3 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
取顶第 2 轮：把堆顶 5(当前最大)和堆的最后一格 下标 4=1 交换，最大值即将归位到尾部。
最大值 5 归位到下标 4，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…3。
新堆顶下沉：看父亲(橙)下标 0=1 和它的孩子下标 1=4、下标 2=3：较大的孩子是下标 1=4，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 4。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
新堆顶下沉：看父亲(橙)下标 1=1 和它的孩子下标 3=2：较大的孩子是下标 3=2，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 1 处坐着更大的 2。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
新堆顶下沉：看父亲(橙)下标 3=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
取顶第 3 轮：把堆顶 4(当前最大)和堆的最后一格 下标 3=1 交换，最大值即将归位到尾部。
最大值 4 归位到下标 3，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…2。
新堆顶下沉：看父亲(橙)下标 0=1 和它的孩子下标 1=2、下标 2=3：较大的孩子是下标 2=3，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 3。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
新堆顶下沉：看父亲(橙)下标 2=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
取顶第 4 轮：把堆顶 3(当前最大)和堆的最后一格 下标 2=1 交换，最大值即将归位到尾部。
最大值 3 归位到下标 2，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…1。
新堆顶下沉：看父亲(橙)下标 0=1 和它的孩子下标 1=2：较大的孩子是下标 1=2，父亲更小，需要交换。
交换：父亲和较大的孩子换位，现在下标 0 处坐着更大的 2。被换下去的 1 继续往下沉，看它还压不压得住孙辈。
新堆顶下沉：看父亲(橙)下标 1=1 和它的孩子：父亲已经是其中最大，不用动，下沉结束。
取顶第 5 轮：把堆顶 2(当前最大)和堆的最后一格 下标 1=1 交换，最大值即将归位到尾部。
最大值 2 归位到下标 1，标绿表示它已经排到了正确位置，之后不再参与。堆的范围缩小到下标 0…0。
堆里只剩下标 0 一个元素，它自然就是最小值，留在最前面。整个数组已经从小到大排好。
三个高频追问：稳定性、建堆为何 O(n)、以及和快排的取舍。
参考代码
def heap_sort(nums): n = len(nums) def sift_down(i, end): # 下沉：父若小于较大孩子则换 while 2*i+1 <= end: big = 2*i+1 if big+1 <= end and nums[big+1] > nums[big]: big += 1 if nums[i] >= nums[big]: break nums[i], nums[big] = nums[big], nums[i] i = big for p in range(n//2-1, -1, -1): # 建大顶堆 sift_down(p, n-1) for end in range(n-1, 0, -1): # 反复取顶 nums[0], nums[end] = nums[end], nums[0] sift_down(0, end-1) return nums复杂度
- 时间：O(n log n)，建堆 O(n)；之后取顶 n-1 次，每次下沉 O(log n)，合计 O(n log n)
- 空间：O(1)，原地交换，只用常数个临时变量，不开额外数组（迭代版下沉无递归栈）
易错点
面试追问把动画讲成自己的话
追问堆排序是稳定排序吗？
追问建堆的时间复杂度为什么是 O(n) 而不是 O(n log n)？
追问堆排序和快速排序怎么选？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题