多组合并使用二进制堆 [英] Multiple Array Merge Using Binary Heap

问题描述

整数鉴于ķ排序数组，每个包含元素的未知正数（不一定元件，每个阵列中的相同数量），其中元件在所有的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).

这篇关于多组合并使用二进制堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！