Merge K-sorted Arrays
Problem :
Given k sorted arrays of size n, merge all the k arrays into one sorted array.
Example :
var n_k_arr = [ [ 8, 10, 12 ], [ 6, 9, 13 ], [ 14, 19, 20] ];
output = [ 6, 8, 9, 10, 12, 13, 14, 19, 20 ];
Naive Solution :
- Merge all the elements into a single array which takes O (nk) time
-
Sort the nk size array which take O( nk log(nk) )
Efficient Solution :
We can merge arrays in O( nk log(k) ) time using Min Heap. Following is detailed algorithm.
- Create an output array of size nk
- Create a min heap of size k and insert 1st element in all the arrays into the heap
- Repeat following steps nk times
- Get minimum element from heap ( which takes constant time ) and store it in output array.
- Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree