sorting - 使用 O(1) RAM 合并数据流

Question

如何使用 O(1) RAM 合并 k 个排序的数据流？我应该如何定义数据流对象及其相关功能/操作？

我的解决方案：嗯，我想到了使用数组列表作为数据流对象。我计划找到 k 个数组列表的第 0 个索引的最小值。应该从该数组列表中删除最小值，并将其放入输出数组列表中。应该重复这个过程，直到所有 k 个数组列表都变为空。但我想这需要 O(k*length of each array list)。任何想法如何在 O(1) 中做到这一点？

Answer 1

制作 O(1) ram 算法在很大程度上取决于您选择的基础数据结构和语言。假设您知道如何使用 O(1) ram 操作数据结构，请参见：

http://en.wikipedia.org/wiki/Merge_sort

合并函数占用 O(1) 内存。现在您所需要的只是对您的数据流集的索引，并将所有流合并到第一个流中，您就完成了。