Heaps - Merge K Sorted Arrays

I am stuck, please help. I can’t get how we can do it with pairs. So, i tried without it.

@MadHawk
You need to make a heap of pair or some structure . Your approach is wrong and this question cannot be solved this way.
Make a priority queue of pairs of integers
The first element of the pair represents the data element and the second element represents the name of the array.
Since there are are multiple arrays to be taken as input , we would take a multidimension array as input where each row would represent an array in itself. The name of the array ( second part of the pair ) would have the row index for this 2-D input array.
Push the first element of each array into the heap as a pair where first part is the data and the second part is the name of the array.
Pop one element at a time from the heap , read it. Push the data element into your final sorted array and then read the second part of the pair i.e. name of the array.
Make another pair of the next element of that same array , since you can find it using the name of the array. If the array has ended just push INT_MAX. The new pair would still be like <data,name> .
Repeat this process for ‘size’ no of times where
size = sum of sizes of all 1-D arrays.
This will be the size of your final sorted array.

Try this out and let me know if you face any problems.

1 Like

So, the pair should contain one int for the data and string for the name of the array?

No the pair would <int,int> only.
The name refers to the index of that array in the main 2-D input array.

1 Like

Thank you!
I will try the question again.
I wanted to ask something apart from this topic- it has been 5 months since I first started c++ from CB only but I really struggle with questions and new topics. What would you suggest how should I move ahead, watch all the videos then do all questions or do ques. topic wise?

@MadHawk
Go topic wise.
When I started a new topic , I watched all its videos then tried all its questions. Make notes while watching the videos. Note down important details and codes. They are really helpful.

1 Like