8.7.3 败者树

败者树用于k路归并，内部结点记录比较失败者，根上方保留全局胜者。输出一路元素后，只沿该叶到根重赛，单次选择O(logk)。

手工推演与代码

四路当前头1,4,2,3，胜者1；该路更新为5，只需与路径对手重赛，下一胜者2。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。把败者树当堆整体重建；未给耗尽归并段设置无穷大哨兵。

迁移训练

k=8时每输出一个元素需数量级多少次比较？答案O(log8)=O(3)。