8.7.3 多路平衡归并与败者树

教材导航 · 第8章

原书定位

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

从 kk 个段首逐一扫描选择最小者,单次需 k−1k-1 次比较;用锦标赛结构保存上次比较信息,可把后续选最小的更新降为 O(log⁡k)O(\log k)。

败者树在内部结点记录比较的失败者,最终胜者单独保存。输出当前最小记录后,只替换其所在段的段首,并沿该叶到根重新比赛;其他分支的结果可复用。它主要降低内存比较成本,减少 I/O 仍依靠归并趟数的变化。

五路归并败者树的建立与更新

五路归并败者树的建立与更新,原书P389。

对应练习

8.7 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P388,PDF第400页

原书对照,原书P389,PDF第401页