使用二叉堆合并多个数组

Question

4

给定k个已排序的整数数组，每个数组包含一个未知正元素数量（不一定是每个数组中的元素数量相同），其中所有k个数组中的元素总数为n，编写一个算法将这k个数组合并为一个包含所有n个元素的已排序数组。

该算法的最坏时间复杂度应为O(n∙log k)。

- Alex

3

假设有 k 个作业任务，每个任务难度未知（不一定不同），其中所有 k 个作业任务的总难度为 n。通常情况下，自己完成作业会更有益。 - flight

1

为了维护提问者的权益，需要说明一下，作业标签是由另一个用户添加的（可能是猜测性地添加的）。 - dsg

1

哈哈，没错。但这句话也可以用于任何问题。 - dsg

1

最近有类似的问题被问到了：http://stackoverflow.com/questions/5436523/merging-sorted-arrays-without-using-a-sort-function-in-java - 也可以看看那里的答案。 - Thomas Mueller

1

@dsg 我知道，这就是为什么我写了“类似”的原因 :-) - Thomas Mueller

显示剩余2条评论

2个回答

0

也许只是因为不变量是堆包含尚未清空的数组中最小的元素。当您尝试从列表i中弹出一个项目时，如果此列表为空，则继续从堆中弹出元素。

- stringofquarks

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dsg · Accepted Answer

将k个排序列表命名为1到k。

令A为合并后的排序数组名字。

对于每个列表，弹出中的项v并将(i, v)压入最小堆中。现在堆包含每个列表中最小条目的值和列表ID的对。

只要堆不为空，就从堆中弹出(i, v)并将v附加到A中。弹出列表中的下一项（如果不为空），并将其放入堆中。

从堆中添加和删除元素共进行了n次操作。堆在每个时间步骤最多包含k个元素。因此，运行时间为O(n log k)。