问题描述
整数鉴于ķ排序数组，每个包含元素的未知正数（不一定元件，每个阵列中的相同数量），其中元件在所有的k阵列的总数为n时，给予的算法合并ķ阵列到单个排序的数组，包含所有n个元素。该算法的最坏情况下的时间复杂度应为O（n∙日志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).
推荐答案
名称的K-排序的列表1，...，K。
Name the k-sorted lists 1, ..., k.
让 A 是合并排序数组的名称。
Let A be the name of the combined sorted array.
对于每一个名单，我，弹出 v 关闭我推（我，V）成分堆。现在堆将包含在每个列表中的对价值和列表ID为最小的项目。
For each list, i, pop v off of i and 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.
而堆不为空，弹出（I，V）从堆和追加 v 到 A 。流行的下一个项目关闭列表我（如果它不为空），并把它放在堆中。
While the heap is not empty, pop (i, v) from the heap and append v to A.Pop the next item off list i (if it's not empty) and put it in the heap.
有 N 添加和移除从堆中。堆至多包含 K 在每个时间步长的元素。因此，运行时间 O（N日志K）。
There are n additions and removals from the heap.The heap contains at most k elements at every time step.Hence the runtime is O(n log k).
这篇关于多组合并使用二进制堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！