前情回顾

image.png
败者树是用来减少内部排序所需时间的一种方法。一般来说，使用k路平衡归并所需的对比次数为k-1次，而使用败者树可以减少该次数。

败者树定义

胜者晋升，摆着留级。有点像争霸赛。
image.png
image.png
如果此时冠军退赛（放弃冠军），而新加入了一个成员。则不需要从新再比拼最开始那么多次数。只需要让新加入的选手与冠军比拼过的选手进行比赛即可。从而大大减少了比赛次数。此思路可以用于外部排序。

用败者树实现多路平衡归并

image.png
如上，以各归并段的第一个关键字先构造一个败者树。非根节点（失败结点）保持失败元素所在的归并段。
image.png
经过七次关键字对比找到了最小关键字1。
image.png
image.png
按照归并排序的规则，还需要从归并段中选出最小的关键字。让归并段3中的下一个元素替代1的位置参与败者树的构建。此时就可以根据之间建立的败者树为基础,让该关键字让之前与1对比过的关键字进行对比即可。
image.png
image.png
其余关键字基于以上类似操作。

败者树可以看作一个完全二叉树（不包括最上面的那个结点）。则k路归并只需对比关键字次数log2k(向上取整)次。

败者树的实现思路

直接不会

总结

image.png