Implement an Onlgk algorithm for the following picture Imple

Implement an O(nlgk) algorithm for the following picture:

Implement a O(nl gk) algorithm to merge k sorted lists into a single list, where n is the total number of elements of all k lists.

Solution

Please find below the algorithm for this problem keeping in mind, we have k sorted lists and a total of n values:

lists[k][?] // This is where we input lists
c = 0 // index in result
result[n] // This is where the output will be displayed
heap[k] // stores index and applicable list and uses list value for comparison

// If i is the index and k is the list, then it will have functions - insert(i, k) and deleteMin() which returns i,k.
// The only reason of using the index and the list, instead of just the value is, so that we can get the successor of any value

// This will populate the initial heap
for i = 1:k // This will run O(k) times
heap.insert(0, k) // O(log k)

// This will keep doing this - delete the minimum and insert the next value from that list into the heap
while !heap.empty() // runs O(n) times
i,k = heap.deleteMin();   
result[c++] = lists[k][i]
i++
if (i < lists[k].length) // This will insert if this is not the end of list
heap.insert(i, k) // O(log k)

Hence, The total time complexity is then O(k*logk+n*2logk)=O(nlogk)