Give an Okn algorithm that merges k sorted lists with a tota

Give an O(kn) algorithm that merges k sorted lists with a total of n elements into one sorted list.

Solution

Heap is the ideal data structure to achieve this. So we will use min heap to merge the lists

1. Create a min heap H having size k and insert 1st elements of all the arrays into a the heap
2. Repeat steps 3 and 4 n*k times.
3. Get minimum element from heap (for min heap minimum is always at root) and store it in output array.
4. Replace heap root with next element from the array  then, heapify the tree. If the array doesn’t have any more elements, then replace root with infinite.

ALgorithm to heapfy