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).
-
3Given k homework tasks, each of unknown difficulty (not necessarily differing), where the total difficulty of all k homework tasks is n, it is usually beneficial to do your homework yourself.flight– flight2011-03-27 00:46:59 +00:00Commented Mar 27, 2011 at 0:46
-
1In defense of the OP, the homework tag was added by a different user (possibly speculatively).dsg– dsg2011-03-27 01:00:53 +00:00Commented Mar 27, 2011 at 1:00
-
1Haha, true. But that could be said for any question.dsg– dsg2011-03-27 02:42:26 +00:00Commented Mar 27, 2011 at 2:42
-
1A similar question has been asked recently: stackoverflow.com/questions/5436523/… - see also the answers thereThomas Mueller– Thomas Mueller2011-03-27 08:38:06 +00:00Commented Mar 27, 2011 at 8:38
-
1@dsg I know, that's why I wrote 'similar' :-)Thomas Mueller– Thomas Mueller2011-03-28 04:09:01 +00:00Commented Mar 28, 2011 at 4:09
|
Show 2 more comments
2 Answers
Name the k-sorted lists 1, ..., k.
Let A be the name of the combined sorted array.
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.
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.
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).
1 Comment
Hengameh
Great solution! But what about the heapify operation at every step? I think time complexity will be O(nk logk)
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.
