Question

As we saw in class, the Mergesort algorithm relies on the Merge procedure that merges two sorted arrays into a single sorted array. A commonly encountered problem is one of merging ‘ P , sorted arrays into a single sorted array, where" (n, , is the total number of elements in all the input arrays together. Design the most efficient algorithm that you can to do this? (Hin: Think about using a min-heap.)

Answer 1

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.

Step-by-step 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!