专题进阶 · 排序算法推荐总顺序 · 第 30 / 148 课

分清有效堆区与有序后缀,利用堆顶反复放置最大值。

先学会这些,再进入本课 堆
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 排序算法

堆排序Heap Sort

建最大堆后不断交换堆顶到末尾并下沉,最坏 O(n log n),通常不稳定。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

分清有效堆区与有序后缀,利用堆顶反复放置最大值。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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. 下沉前两棵子树满足堆性质,交换较大孩子后只可能继续破坏更下面一层。
  2. 每轮把有效堆的最大值放到其末尾,且它不大于已有后缀中的值。
  3. 边界缩到 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

最大堆为什么产生升序结果?

需要一点提示

最大值放在哪端?

查看解析与答案

不断放到右端,且之后不再移动,最终左小右大。

练习 2 · 边界与辨析

仅一个元素会越界吗?

需要一点提示

看两个 range。

查看解析与答案

两个循环都为空,直接返回副本。

练习 3 · 变式与迁移

若只需要最大的 10 个元素,是否必须完成全部轮次?

需要一点提示

结果已在右侧。

查看解析与答案

完成 10 次取顶即可,建堆 O(n) 加取顶 O(10 log n);也可用容量 10 的小根堆处理流。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 排序

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。