Merge k sorted arrays- heaps

#1

Is the logic good or optimized which i am using in this code?

#2

@Rishab
No , this logic , though it works for small inputs is not ideal.
The time complexity for this approach is O( nk log(nk) ). Moreover you need to make a priority queue of size = nk which also increases the space complexity.
This problem can be solved in O(nk log(k) ) time with a heap of size = k.

Try to think of a better approach for this problem. Let me know if you need some hints for the same.

#3

I have tried to implement this logic but i am unable to implement it.
Can you refer the code for this type of implementation?

#4

@Rishab
I cannot provide you with the solution code as that would defy the purpose of learning entirely.
I can help you with the approach though.

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.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.