Merging multiple arrays using a binary heap

Question

For k sorted arrays of integers, each of which contains 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 k arrays into one sorted array containing all n elements. The worst-case time complexity algorithm should be O (n ∙ log k).

Answer 1

What are the k-sorted lists 1, ..., k.

Let A be the name of the combined sorted array.

For each list i, pop v off i and press (i, v) in the mini-heap. Now the heap will contain pairs of values ​​and a list identifier for the smallest entries in each of the lists.

Until the heap is empty, pop (i, v) from the heap and add v to A Select the next off list i item (if it's not empty) and put it in a heap.

On the heap, n added and deleted. A heap contains no more than k elements at each time step. Therefore, the runtime is O(n log k) .

Answer 2

Perhaps the just invariant is that the heap contains the smallest elements from the arrays that were not empty. When you try to pull an item from list i, if this list is empty, you keep popping items from the heap.