在multiway merge中任务是从k个元素中找出最小的元素
解决方案:优先队列
想法:从前 k 次运行中取出最小的元素，将它们存储到堆树中的主内存中。
然后反复从堆中输出最小的元素。最小的元素被替换为它来自的运行中的下一个元素。
完成第一组运行后，对下一组运行执行相同的操作。
假设我的主内存大小 ( M ) 小于 k，我们如何对元素进行排序，换句话说，如果内存大小 M 小于 K，多路合并算法合并如何工作
例如，如果我的 M = 3 并且我有以下内容
磁带 1:8 9 10 磁带 2:11 12 13 磁带 3:14 15 16 磁带 4:4 5 6
我的问题是 muliway merge 将如何工作，因为我们将读取 8、11、14 并构建优先级队列，我们将 8 放置到输出磁带然后转发 Tape1，我不知道何时读取 Tape4 以及我们将如何与已经进行比较写入输出磁带？
谢谢!
最佳答案
这是行不通的。您必须为可用内存选择足够小的 k。
在这种情况下，您可以对前 3 个磁带进行 3 向合并，然后在其结果与剩余磁带之间进行 2 向合并。或者您可以进行 3 次双向合并(两对磁带，然后合并结果)，这实现起来更简单，但需要更多的磁带访问。
理论上你可以放弃优先队列。这样你就不需要在内存中存储 k 个元素，但你会经常需要查看所有 k 磁带上的下一个元素以找到最小的元素。
关于algorithm - 外部排序 : multiway merge，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7609955/