8.7.3 多路平衡归并与败者树
原书定位
印刷页P388起,对应PDF第400页。下文为目视整理的知识提要;完整内容见原书对照。
从 个段首逐一扫描选择最小者,单次需 次比较;用锦标赛结构保存上次比较信息,可把后续选最小的更新降为 。
败者树在内部结点记录比较的失败者,最终胜者单独保存。输出当前最小记录后,只替换其所在段的段首,并沿该叶到根重新比赛;其他分支的结果可复用。它主要降低内存比较成本,减少 I/O 仍依靠归并趟数的变化。

五路归并败者树的建立与更新,原书P389。
对应练习
关联知识
原书对照
展开原书对照截图

