外部排序：多路合并

Question

在多路合并的任务是找到最小的元素从k个元素的

解决办法：优先级队列

理念：以来自前k运行的最小元素，并将其存储到堆树中的主内存。

然后重复输出堆中最小的元素。最小的元素将被来自其运行的下一个元素替换。

完成第一组运行后，对下一组运行进行同样的处理。

假设我的尺寸的主内存（M）小于K，我们如何才能要素，换句话说，路合并算法如何多合并作品进行排序，如果内存大小M是少于k个

例如，如果我的M = 3，我已经以下

TAPE1：8 9 10 TAPE2：11 12 13 Tape3：14 15 16 Tape4：4 5 6

我的问题如何muliway合并将工作，因为我们将读8,11,14并建立优先队列，我们​​放置8输出磁带，然后转发Tape1 ，当Tape4被读取时，我没有得到什么，我们将如何比较已经写入输出磁带？

谢谢！

Answer 1

它不起作用。您必须选择足够小的可用内存的k。

在这种情况下，您可以执行前3个磁带的3路合并，然后在该结果和剩余磁带之间进行双向合并。或者你可以做3个2路合并（两对磁带，然后合并结果），这是更容易实现，但更多的磁带访问。

理论上你可以放弃优先队列。然后，您不需要在内存中存储k元素，但您经常需要查看所有k磁带上的下一个元素才能找到最小的元素。