败者树

败者树

作用：在外部排序方法中，为了减少I/O次数，而需要将二路平衡归并改为多路平衡归并，但是按照原有的归并算法，将二路归并改为多路归并将增加其内部排序的时间。为了是内部排序不受到归并数目的影响，从而引入了败者树的概念。

概念：败者树是对树形选择排序的一种变化，它是一颗完全二叉树。每个叶子节点存放各个归并段在当前位置需要参加归并的记录，其内部节点用来记录左右子数中的“失败者”，从而让胜利者继续比较，一直到跟节点。根据需求可以将左右子数中大的（小的）定义为失败者，小的（大的）为胜利者，则根节点指向的数为最小数（最大数）。

下面以大的为失败者，小的为胜利者解释。

如上图所示：有b0、b1、b2、b3、b4五个归并路数，它们的值分别是10、9、20、6、12.首先看b3和b4比较，b3为胜利者，于是将失败者b4的路号4存入b3、b4的父节点中；将胜利者b3继续与b0相比，b3对应的是6，b4对应的是10，于是b3为胜利者，b0为失败者，将失败者b0的路号0存入到上一层父节点中；再看右边b1和b2的比较，b1对应的是9，b2对应的是20，于是b1为胜利者，b2为失败者，将失败者b2的路号2存入到b1、b2的父节点中；然后将左边的胜者b3与右边的胜者b1比较，b3对应的是6，b1对应的是9，则b3为胜者，b1为败者，将失败者b1的路号1存入到上一层父节点中；最后在将胜利者的路号写入ls[0]中。