8.4.2.3 堆的应用与性能
原书定位
印刷页P361起,对应PDF第373页。下文为目视整理的知识提要;完整内容见原书对照。
求海量数据中最大 个,用容量 的小根堆,堆顶为候选中最小者;求最小 个则用大根堆。后续记录优于堆顶时替换并调整,时间 、空间 。
如果需要前 个最小值的有序输出,也可先建全量小根堆,再出堆 次,时间 。候选堆内部仅满足堆序,若要求最终排序还需额外处理。
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P361起,对应PDF第373页。下文为目视整理的知识提要;完整内容见原书对照。
求海量数据中最大 个,用容量 的小根堆,堆顶为候选中最小者;求最小 个则用大根堆。后续记录优于堆顶时替换并调整,时间 、空间 。
如果需要前 个最小值的有序输出,也可先建全量小根堆,再出堆 次,时间 。候选堆内部仅满足堆序,若要求最终排序还需额外处理。
