Heaps: Merge “K” sorted arrays

Problem Statement:

You are given k sorted arrays of size n each.
You need to merge them and print the sorted output.

Example

k = 3, n = 4 
arr[][] = { {1, 3, 5, 7}, 
			{2, 4, 6, 8}, 
			{0, 9, 10, 11}} ;

Output: 0 1 2 3 4 5 6 7 8 9 10 11

Solution

We will use min heap to solve this problem.

Create a min heap and insert all the k arrays.

Then start removing the top elelemt from the heap till it becomes 0.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;

#define n 4


void merge_K_Arrays(int arr[][n], int k)
{
    priority_queue<int, vector<int>, std::greater<int> >pq;
    for(int i=0; i<k; i++)
    {
        for(int j=0; j<n; j++) 
            pq.push(arr[i][j]);
    }

    cout<<"sorted array = ";
    while(pq.size())
    {
        cout<<pq.top()<<" ";
        pq.pop();
    }
}


int main()
{
    int arr[][n] =  {{2, 6, 12, 34},
                     {1, 9, 20, 1000},
                     {23, 34, 90, 2000}};

    int k = sizeof(arr)/sizeof(arr[0]);

    merge_K_Arrays(arr, k);

    return 0;
}

Output:

sorted array = 1 2 6 9 12 20 23 34 34 90 1000 2000