8.4.2.3 堆的应用与性能

教材导航 · 第8章

原书定位

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

求海量数据中最大 kk 个,用容量 kk 的小根堆,堆顶为候选中最小者;求最小 kk 个则用大根堆。后续记录优于堆顶时替换并调整,时间 O(nlog⁡k)O(n\log k)、空间 O(k)O(k)。

如果需要前 kk 个最小值的有序输出,也可先建全量小根堆,再出堆 kk 次,时间 O(n+klog⁡n)O(n+k\log n)。候选堆内部仅满足堆序,若要求最终排序还需额外处理。

对应练习

8.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P361,PDF第373页