http://data.biancheng.net/view/77.html
-
目的类似大小顶堆输出最大/最小值，保留了之前的比较结果，比堆更能减少比较次数。
-
节点存放胜者为胜者树，存放败者为败者树
胜者树：
是树形选择排序的一种变形，本身是一棵完全二叉树。
胜者树：在树形选择排序一节中，对于无序表{49，38，65，97，76，13，27，49}创建的完全二叉树如下图所示，构建此树的目的是选出无序表中的最小值。
胜者树.png
败者树：
而败者树恰好相反，其双亲结点存储的是左右孩子比较之后的失败者，而胜利者则继续同其它的胜者去比较。
所示为一棵 5-路归并的败者树，其中 b0—b4 为树的叶子结点，分别为 5 个归并段（已经预先排好了序）中存储的记录的关键字。
败者树
-
注：为了防止在归并过程中某个归并段变为空，处理的办法为：可以在每个归并段最后附加一个关键字为最大值的记录。这样当某一时刻选出的冠军为最大值时，表明 5 个归并段已全部归并完成。（因为只要还有记录，最终的胜者就不可能是附加的最大值）
-
存储：
败者树是完全二叉树， 因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k- 1]为比较结点，b[0]--b[k-1]为叶子结点。另外b[k]为一个附加的辅助空间，不属于败者树，初始化时存着MINKEY的值。
- 败者树分段示例：
待排数据：
image.png
由败者树得知，其最终胜者为 29，设为 MINIMAX 值，将其输出到初始归并文件中，同时再读入下一个记录 14（所有等待中的段头元素中的最小值），调整败者树：
image.png
当进行关键字的比较时，先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。（序号一开始都初始化为0，相当于段号）
通过不断地向败者树中读入记录，会产生多个 MINIMAX，直到最终所有叶子结点中的序号都为 2，此时产生的新的 MINIMAX 值的序号 2，表明此归并段生成完成，而此新的 MINIMAX 值就是下一个归并段中的第一个记录。
网友评论