批量建堆：一次建成一个堆
看完你能说清 O(n) 建堆为何成立，并亲手推一遍自底向上下沉的全过程
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
批量建堆：一次建成一个堆
看完你能说清 O(n) 建堆为何成立，并亲手推一遍自底向上下沉的全过程
问题设定：从空堆出发
前面说过堆的增删都要维护堆序。那如果手里有 n 个乱序元素，怎么得到一个堆？最直觉的做法：想象一个空堆，把元素一个接一个插进去，每插一个就向上调整一次——插完全部，自然就是个堆。
每插一本都插到当前合适位置，书架始终保持有序
自上而下的上滤：算法
逐个插入建堆：每个新元素从底部出发，一路与父结点比较上滤到位。
上滤的图解过程
数组 [9,4,7] 建成堆后插入 1，绿色是 1 沿父链逐层上滤的路径，逐帧看它怎么爬到根。
自上而下的上滤：代码
逐个 insert 的循环，配上上滤的核心代码，看每个新元素如何逐层上浮。
外层循环逐个 insert；percolateUp 只与新元素 x 反复比较：父大则父下移，最后 x 一次性落位，而非逐步交换。
上滤的效率分析
前面几页我们用上滤逐个插入元素建堆。方法是对的，但每插一个都可能一路换到根。到底一共要换多少次？把每个元素 worst case 上升的层数加起来，代价会惊人。
为什么 O(n·logn) 不划算
上滤建堆已是 O(nlogn)，看似不差——但和直接排序同阶，作为预处理毫无意义，这是最容易忽略的对比基准。
- 复杂度 O(n·logn)，n 大时 ≈ n log n
- 只得到一个堆，内部仍无序
- 之后还得再排序才能输出全序
- 复杂度 O(n·logn)，同样 n log n
- 建堆只是排序的第一步
- 一次流程直接输出有序结果
换个思路：自下而上
上一页我们算清了：从空堆逐个插入要 O(n·logn)，不划算。那换个角度——不如先把 n 个元素原封不动按完全二叉树的形状摆好，形状不用花钱，再想办法把堆序补上。
先大致摆放书架再逐格调整，对应先摆形状再下滤
自下而上的下滤：算法
从最后一个内部结点倒着做下滤，子堆逐层合并成完整堆。
下滤建堆：完整实例
从右往左看五个状态框：每框是数组的当前形态，箭头标注本次下滤发生在哪个结点、和谁交换。
实例续：关键步骤拆细
看根节点4的一次下滤：每层只在两个孩子里取大者比较交换，直到堆性恢复。
自下而上的下滤：代码
用真实的 Python 代码看 heapify 的核心循环：从最后一个内部节点倒着做下滤。
第 13 行取 ⌊n/2⌋：叶子无需下滤；第 14 行倒序遍历，先建好子堆，大节点才能一路沉底。
下滤建堆：效率 O(n)
前面实例里下滤建堆看着也是逐个下滤，似乎仍是 n 次 O(log n)？关键区别在于：下滤的代价由结点高度决定，而堆里大多数结点根本没那么高。
占多数的基层员工随口附和即可，管理层少数人才需要长篇发言
两种策略正面对比
同样是建堆，代价为何差出整整一个 log n？关键在多数结点离根近还是离底近。
- 方向：从浅到深，逐个插入
- 代价集中：深层结点多，滤得远
- 总计：O(n·logn)，不划算
- 方向：从深到浅，逐个下滤
- 代价集中：底层结点多，滤得少
- 总计：O(n)，线性完成
自测：建堆策略的选择
对同一组 n 个元素批量建成完全二叉堆，自下而上下滤通常优于自上而上滤，根本原因是什么？
要点收束
- ✓上滤逐个插入，成本Σlogi≈O(nlogn)
- ✓下滤只对非叶结点工作，省一半
- ✓建堆下滤从⌊n/2⌋−1逆序到0
- ✓下滤成本按高度求和，总和O(n)
- ✓n越大，O(n)建堆优势越显著
课后思考
先自己推一推、画一画，再对照参考答案，看看思路差在哪。
参考答案按高度分层：第 h 层约 n/2^(h+1) 个节点，各下滤 h 步。求和得 Σ n·h/2^(h+1)，是常数倍收敛级数，故总量 O(n)。关键在多数节点下滤距离极短。
参考答案满堆与退化堆的节点数固定时，逐层高度结构不变，O(n) 几乎不变；对比上滤的 O(n·logn) 差距才是重点。说明下滤建堆对输入分布不敏感，稳定性好。
参考答案内部节点编号最大为 ⌊n/2⌋，其后全是叶子，叶子无需下滤。从 n 开始会对叶子空做下滤，从更小开始会漏掉某个内部节点，堆性质不完整。