Answer:
We need to merge ordered arrays. We must first store the first element of the k matrices in the minimum heap. So we get to have the minimum element at the top, then we take out the element and place the next element in the matrix in the minimum heap.
Explanation:
Psuedo Code:
our min heap node has got the following structure:
int value;
int array_num;
int aray_index;
void mergeKArrays(int [][] arr, int k, int n) {
// define new min heap
min_heap = new MinHeap()
for(int i=0;i<k;i++)
min_heap.insert({
value: arr[i][0],
array_num : i,
array_index: 0
})
int finalArray[n*k]
finalArrayIndex =0;
// keep popping the min heap and insert the new element
while(!min_heap.isEmpty()) {
topNode = min_heap.pop();
finalArray[finalIndex++] = topNode.value
// if we are already at the last element of array then we cannot insert the next element, so for safety
if(topNode.array_index + 1 < n) {
min_heap.insert({
value: arr[topNode.array_num][topNode.array_index + 1],
array_num: topNode.array_num,
array_index: topNode.array_index+1
})
} else {
// choose a random array index and insert its element
int randomIndex = random();
min_heap.insert({
value: arr[randomIndex][topNode.array_index + 1],
array_num: randomIndex,
array_index: topNode.array_index+1
})
}
}
// print the final array
for( int i=0;i<n*k;i++)
print(finalArray[i])
}
Hope this helps!
