8-13外部排序-败者树

败者树是树形选择排序的一种变体，可视为一棵完全二叉树

绿色为叶子结点，存放初始数据
黑色为失败结点
蓝色为胜出结点

一.基本过程
以下按从小到大的方式构建

1.从8个归并段中选择第一个元素放入绿色结点，进行第一次比较

两两比较，输的（大的）留下，赢的（小的）上去

右边同样

但结点中标记的不是关键字的值，而是来自哪个归并段

如图，1是最小的，来自归并段3，因此最上面的结点记录的是3

至此，一共8个归并段，通过8-1=7次关键字的对比找到的最小的元素

将1拿出，归并段3的下一个关键字6上绿色结点

只需进行3次关键字的对比即可选出下一个最小元素

可以看出，从第二次起，对比关键字的次数从（归并段数-1）变为了黑色的层数（3层）

败者树的实现.cpp

cpp 0星 超过10%的资源 2KB

下载

选出第二个元素，归并段5的元素2

因此，对于k路归并，第一次构造败者树需要对比关键字k-1次，后续选最小元素至多需要对比关键字⌈$lo{g}_{2}k$⌉次
（至多：对于非满二叉树在右侧插入）

理由：将黑色和绿色结点看成一棵树，树高h，则从第二轮起对比次数为h-1次，而第h层的结点数等于归并段数k，有k≤$2^{h-1}$，当k=$2^{h-1}$时有h-1=⌈$lo{g}_{2}k$⌉

此外，叶子结点的虚拟的

ls数组按层序遍历，从根节点开始依次编号（忽略最上面的结点），ls[0]为胜出结点，ls[1-4]对应失败结点，数组中不包括待比较的叶子结点b_i

在下图中b₀所在归并段0，b₁所在归并段1，以此类推

失败层数⌈$lo{g}_{2}k$⌉=⌈$lo{g}_{2}5$⌉=3

败者树使用多路平衡归并，大大减少了归并趟数

回顾：原来每次选出最小元素都需要k-1次
多路平衡归并
①最多只能有k个段归并为一个
②每一趟归并中，若有m个归并段参与归并，则经过一趟处理得到⌈m/k⌉个新的归并段