使用二叉堆合并多个数组
给定 k 个已排序的整数数组，每个数组包含未知的正数元素（每个数组中的元素数量不一定相同），其中所有 k 个数组中的元素总数为 n，给出将 k 个数组合并为的算法单个排序数组，包含所有 n 个元素。 该算法的最坏情况时间复杂度应为 O(n∙log k)。
Given k sorted arrays of integers, each containing an unknown positive number of elements (not necessarily the same number of elements in each array), where the total number of elements in all k arrays is n, give an algorithm for merging the k arrays into a single sorted array, containing all n elements.
The algorithm's worst-case time complexity should be O(n∙log k).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
将 k 排序列表命名为 1, ..., k。
令
A为组合排序数组的名称。对于每个列表 i，将
v从i中弹出，并将(i, v)压入最小堆。现在，堆将包含每个列表中最小条目的值和列表 id 对。当堆不为空时，从堆中弹出
(i, v)并将v附加到A。从列表
i中弹出下一个项目（如果它不为空）并将其放入堆中。堆中有
n次添加和删除。堆在每个时间步最多包含
k个元素。因此，运行时间为
O(n log k)。Name the k-sorted lists 1, ..., k.
Let
Abe the name of the combined sorted array.For each list, i, pop
voff ofiand push(i, v)into a min-heap. Now the heap will contain pairs of value and list id for the smallest entries in each of the lists.While the heap is not empty, pop
(i, v)from the heap and appendvtoA.Pop the next item off list
i(if it's not empty) and put it in the heap.There are
nadditions and removals from the heap.The heap contains at most
kelements at every time step.Hence the runtime is
O(n log k).也许不变的是堆包含尚未清空的数组中的最小元素。当您尝试从列表 i 中弹出一个项目时，如果该列表为空，您将继续从堆中弹出元素。
Maybe just that the invariant is that the heap contains the smallest elements from the arrays that haven't been emptied. When you try to pop an item off list i, if this list is empty, you go on popping elements off the heap.