01先把问题说具体
堆只保证根最大,并不保证整个数组有序。怎样把这个局部保证转成完整排序?
02一步步得到方法
先建堆,再逐个缩小边界
先从最后一个非叶节点向前下沉,建立最大堆。随后堆顶是有效堆区的最大值,把它交换到 end 位置;end 之后的有序后缀从此不再参加堆调整。
交换后根位置可能太小,只需从根向下修复;原来的两个子堆内部没有变化。每次选较大的孩子,确保父节点不小于任何孩子。
为什么必须传入 heap size
数组长度在排序中保持不变,但有效堆长度不断减一。若下沉时仍使用完整 len(a),已经确定的最大元素会被重新拖回堆中,破坏后缀。
堆排序不需要递归分区,因此没有快排那样由分区失衡产生的 O(n²) 最坏时间。不过它的访问局部性和稳定性通常不如某些其他排序,不能只看渐近界选实现。
堆顶就位后为什么缩小边界
最大堆只保证父节点不小于孩子,不保证左右子树按数组顺序有序。每次把堆顶与当前末尾交换,最大值才真正到达最终位置,然后将它排除在堆范围之外。
交换到根的元素可能比孩子小,只需向下恢复根到叶子的一条路径。已就位的后缀不再参与调整,这个堆区与有序区的边界是检查代码正确性的关键。
03把一个小例子完全算清楚
[3,1,4,2] 升序排序。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 建最大堆 | [4,2,3,1] | 根为当前最大值 4 |
| end=3 | 交换并下沉:[3,2,1,4] | 4 离开堆区 |
| end=2 | 交换并下沉:[2,1,3,4] | 后缀 [3,4] 有序 |
| end=1 | [1,2,3,4] | 只剩单元素堆 |
窄屏可左右滑动表格,阅读完整计算与理由。
有序后缀从右向左扩大,最大堆只负责当前尚未确定的部分。
04为什么这个方法成立
- 下沉前两棵子树满足堆性质,交换较大孩子后只可能继续破坏更下面一层。
- 每轮把有效堆的最大值放到其末尾,且它不大于已有后缀中的值。
- 边界缩到 1 后所有位置都已确定。
05把推导翻译成代码
Python · 可独立运行的教学实现
def heap_sort(values):
a = list(values)
def down(root, size):
while 2 * root + 1 < size:
child = 2 * root + 1
if child + 1 < size and a[child+1] > a[child]:
child += 1
if a[root] >= a[child]:
break
a[root], a[child] = a[child], a[root]
root = child
for i in range(len(a)//2 - 1, -1, -1):
down(i, len(a))
for end in range(len(a)-1, 0, -1):
a[0], a[end] = a[end], a[0]
down(0, end)
return a逐个理解关键决定
down(0, end)- end 是排除末尾元素后的堆大小,区间为 [0,end)。
child += 1- 在存在右孩子且更大时改选右侧,避免父节点仍小于另一个孩子。
06时间、空间与实现范围
自底向上建堆 O(n):高节点少、低节点多,不能简单把每个节点都按 log n 计紧界。
之后 n−1 次下沉各 O(log n),总 O(n log n)。核心 O(1) 辅助空间,本函数复制输入 O(n)。
07改变条件,检查哪里会出错
把堆数组直接当作排序结果
堆只约束父子,兄弟之间没有排序要求。
将稳定排序当成默认性质
远距离交换可能改变同键次序,需带原下标作次键或改用稳定算法。
把完整数组长度传给每次下沉
会重新移动已经排好的后缀,应传入当前有效堆大小。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
最大堆为什么产生升序结果?
需要一点提示
最大值放在哪端?
查看解析与答案
不断放到右端,且之后不再移动,最终左小右大。
仅一个元素会越界吗?
需要一点提示
看两个 range。
查看解析与答案
两个循环都为空,直接返回副本。
若只需要最大的 10 个元素,是否必须完成全部轮次?
需要一点提示
结果已在右侧。
查看解析与答案
完成 10 次取顶即可,建堆 O(n) 加取顶 O(10 log n);也可用容量 10 的小根堆处理流。