多通道均衡合并排序算法(多通道合并排序,胜利者树,输家树)

2020-05-23 09:47:45   来源: 网络

通过前面部分对外部排序的介绍,我们知道,对于外部排序算法,直接影响算法效率的因素是读取和写入外部内存的次数,即次数越多,算法的效率...


通过前面部分对外部排序的介绍,我们知道,对于外部排序算法,直接影响算法效率的因素是读取和写入外部内存的次数,即次数越多,算法的效率就越低。如果要提高算法的效率,即在算法的操作过程中减少读写内存的数量,可以在路径平衡合并中增加k值。

然而,计算后发现,如果k值无限制地增加,虽然会减少读取和写入外部数据的次数,但会增加内部合并的时间,这是不值得损失的。

例如,在上一节中,对于10个临时文件,如果您只想从2个文件中获得一个最小值一次,如果您想从2个文件中获得一个最小值,那么如果您想要从5个文件中获得一个最小值,则只需对它进行四次比较。以上只是得到一个最小记录,如果您想得到整个临时文件,那么时间就会非常不同。

为了避免在增加k值的过程中影响内部合并的效率,在进行k-路径合并时可以使用失败树,这种方法在k值增加时不会影响内部合并的效率,输家树实现了丢失树的内部合并,这是树形状选择和排序的一种变形,是一种完整的二叉树本身。

在树选择排序部分,为无序表{49、38、65、97、76、13、27、49}创建的完整二叉树如图1所示,构建该树的目的是在无序表中选择最小值。

这棵树与输家树相反。它是一棵胜利者树。因为树中每个非终端节点(叶节点除外)中的值代表的值比左右侧的子节点(最小的是赢家)小。例如,与叶节点49和38相比,由于38较小,其父节点中的值保留了胜利者38。然后使用38继续与上层进行比较,直到树的根节点。

图1胜利者树

胜利者树和输家树的区别在于,胜利者树中的非终端节点存储胜利方,而输家树中的非终端节点存储失败方。在比较过程中,对胜利者进行比较。

图2失效树

注意:为了防止在归并过程中某个归并段变为空,处理的办法为:可以在每个归并段最后附加一个关键字为最大值的记录。这样当某一时刻选出的冠军为最大值时,表明 5 个归并段已全部归并完成。(因为只要还有记录,最终的胜者就不可能是附加的最大值)

6 9 10 12 15 15 16 18 20 20 22 25 37 40 48