Multiple Array Merge Using Binary Heap

Given k sorted arrays of integers, each containing an unknown positive number of elements (not necessarily the same numb开发者_运维问答er 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).

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).

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.