CODEWITHSUNDEEP
arraysalgorithmmerge
MuleNoob
MuleNoob

Reputation: 127

K way merge of sorted arrays implementation using a min heap

I've been trying to figure out how to implement the following algorithm for a K way merge. 

Algorithm:
1)Initialize an array of size n*k. 
2) Initialize a min heap of size k, to hold the smallest element of each array.
3) Add the smallest element from the minHeap into the output array.
4)Move the next element from the array from which the min element was derived onto the heap. // How would one implement this?
5) Repeat step 4 until all the arrays are empty and the minHeap is empty.

I've been able to implement all but Step 4 of my algorithm. How would one track the array from which the smallest element has been extracted?

Upvotes: 0

Views: 1830

Answers (1)

mr.engineer
mr.engineer

Reputation: 197

Try keeping element and array in pair. Element would be key, array (pointer to it) would be value. Pair should be sortable by it's keys.
When you extract the smallest pair from the heap, you take the key from the pair as the element you wanted, and value in that pair will be array containing that element.

Important: depending of the language you're working with, don't copy the arrays as values, but save only pointers to them (let's say in C++), or their references (i.e. Java).

Upvotes: 2

Related Questions