algorithm - k-way合并中合并和项目数之间的关系是什么

Question

问题是:在 k 路合并中，我们将执行多少次合并操作。 例如:2-way merge:2 nodes 1 merge; 3节点2合并； 4节点3合并。所以我们得到 M(n)=n-1。

当 k 是任意值时，M(n) 是多少？

Answer 1

2-way 合并在合并大小相等的 block 时最有效，因此基于 2-way 合并的最有效的 k-way 合并是先将 block 1 与 block 2、 block 3 合并与 block 4，依此类推，然后合并前两个结果 block ，依此类推。这基本上就是归并排序的工作原理，并导致 O(kn log k) 时间，假设每个 k block 都包含 n 项。但只有当所有 block 都恰好有 n 个项目时，它才会非常有效，并且 k 是 2 的幂，所以...

代替执行 k 个单独的合并 channel ，您可以使用单个 channel ，该 channel 使用包含每个 block 的第一个项目的堆(即总共 k 个项目):

1. 从堆中读取最低项(O(log k) 时间)
2. 写出来
3. 从堆中移除它
4. 如果该项目来自的 block 尚未用完，则将它的下一个项目放入堆中(再次 O(log k) 次)。
5. 重复直到堆为空。

如果总共有 kn 个项目，无论它们如何分布，这总是需要 O(kn log k) 时间 block ，无论 k 是否是 2 的幂。您的堆需要包含 (item, block_index) 对，以便您可以识别每个项目来自哪个 block 。