假设有k个有序序列，我们希望将他们归并到一个单独的有序序列中。归并的任务可以通过循环输出k个序列中键值最小的记录来完成。
最简单的方法是对k个有序序列k-1次进行比较得出最小值，然后循环这个过程。这里能不能优化查找最小值的方式？人民是智慧的，这里可以采用胜者树和败者树来降低查找最小元素所需的比较次数。
胜者树与败者树是完全二叉树。就像是参加比赛一样，每个选手有不同的实力，两个选手PK,实力决定胜负，晋级下一轮，经过几轮之后，就能得到冠军。不同的是，胜者树的中间结点记录的是胜者的标号；而败者树的中间结点记录的败者的标号。 胜者树与败者树可以在log(n)的时间内找到最值。任何一个叶子结点的值改变后，利用中间结点的信息，还是能够快速地找到最值。在k路归并排序中经常用到。
胜者树
胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。下面是选择一个最小的数字为最终胜利者（见图1所示），第一次把各个数组里面的第一个元素都放进去，这是根据胜利树的规则两两比较，得到最小的值，第一次弄完之后，就得出1数字是胜利的，也就是1是最小的。在下一次输出第二小的数字时候，只需要把1所在的数组里面的元素加进去，然后从叶子节点到根节点一直比较得出第二小的值，这样就减少了很多次无用的比较（见图2所示）
图1
图2
败者树
胜者树新加元素后，要先访问父节点然后得到兄弟结点，与兄弟结点做比较后得出新的父节点，然后循环这个过程。有没有进一步优化的可能？有的，那就是败者树。
败者树新加元素后，直接和父节点作比较就可得出新的父节点，节省了胜者树中先访问父节点再找兄弟结点的中间过程，减少了访存时间，提高了效率。
败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程