8.4.2.1 建堆与堆排序
原书定位
印刷页P359起,对应PDF第371页。下文为目视整理的知识提要;完整内容见原书对照。
从最后一个非叶结点向前逐个下滤。大根堆下滤时先比较两个孩子取较大者,再与暂存的根比较,将较大孩子上移,直至根可放入当前位置或到叶层。
自底向上整体建堆为 ,因为多数结点离叶层很近;逐条插入建堆的最坏为 ,二者过程和结果可能不同。
升序排序反复交换堆顶与当前堆尾,将堆大小减 1,再下滤新根。最坏和平均 ,原地迭代下滤空间 ,不稳定。教材将常见互异关键字模型的最好也记作 ;若允许大量等值且下滤提前退出,特定实现可出现更低的具体输入开销。

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

删除堆顶后的下滤,原书P360。
对应练习
关联知识
原书对照
展开原书对照截图

