8.4.2.1 建堆与堆排序

教材导航 · 第8章

原书定位

印刷页P359起,对应PDF第371页。下文为目视整理的知识提要;完整内容见原书对照。

从最后一个非叶结点向前逐个下滤。大根堆下滤时先比较两个孩子取较大者,再与暂存的根比较,将较大孩子上移,直至根可放入当前位置或到叶层。

自底向上整体建堆为 O(n)O(n),因为多数结点离叶层很近;逐条插入建堆的最坏为 O(nlog⁡n)O(n\log n),二者过程和结果可能不同。

升序排序反复交换堆顶与当前堆尾,将堆大小减 1,再下滤新根。最坏和平均 O(nlog⁡n)O(n\log n),原地迭代下滤空间 O(1)O(1),不稳定。教材将常见互异关键字模型的最好也记作 O(nlog⁡n)O(n\log n);若允许大量等值且下滤提前退出,特定实现可出现更低的具体输入开销。

自底向上建大根堆

自底向上建大根堆,原书P359。

删除堆顶后的下滤

删除堆顶后的下滤,原书P360。

对应练习

8.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P359,PDF第371页

原书对照,原书P360,PDF第372页