Merge k sorted arrays

#1

Please provide the code for this program in c++

#2

hello @nidhigupta847

Algorithm

  1. Make a priority queue where each node stores three values - the element itself , its row no. and its col no.
  2. Push the first elements of all the rows into this priority queue with their corresponding row and column info.
  3. One by one , take nodes out of this priority queue and insert their values into the final sorted array.
  4. Also push the next element of the same row using the other information into the priority queue.
  5. Repeat this process till the priority queue gets empty.

code->

1 Like
#3

priority_queue<ppi, vector, greater> pq; could you explain this line ?

#4

its a declaration for min heap,
that line is declaring a min heap of type -> pair<int, pair<int, int>>

refer this ->article

#5

What happens if we do not mention vector ppi ??

#6

that second argument i.e vector< ppi > is the internal underlying container object where the elements are stored.

if u dont mention it then it wll give error

#7

Okay and what is the time complexity of implementing this program using heaps ?

#8

@nidhigupta847
if n is size of each array and if total there are k arrays then time complexity will be

n*k log (k)

1 Like