Merge k sorted arrays - HEAP

#1

Can someone please share the code for Merging k sorted arrays by Priority Queue.
The code in editorial is quite vague.
I understood the concept but unable to implement it.
https://ide.codingblocks.com/s/64516
What I am doing wrong is always putting Int_Max, which is wrong.

#2

Hi Lakshay, what if I say you that in this case consider priority queue to be such a data structure wherein you insert an element and the whole list remains sorted always.
All that you have done after Line 16 is wrong and not required.
You just need to make a min priority queue and take values input in an array a. which is correctly done till line 15.
Now after that start putting elements in the min priority queue from a[] array as:

   for(i = 0; i < k; i++){
        for ( j = 0 ; j < n ; ++j )
        pq.push(a[i][j]);
    }

these 4 lines have sorted your k lists.
Now to print them you just have to show top element and then pop it as:

  for(i = 0; i < k*n ; i++){   //Notice that i: 0 -> k*n
       cout << pq.top() << ' ' ;
       pq.pop() ;
   }

Hope this helps :slight_smile:

1 Like