Merge k sorted arrays -heap

K sorted arrays arranged in the form of a matrix of size K*K. we have to merge them into one sorted array.

Example :

Input:
K = 4
arr[][]={{1,2,3,4}{2,2,3,4},
         {5,5,6,6},{7,8,9,9}}
Output:
1 2 2 2 3 3 4 4 5 5 6 6 7 8 9 9 
Explanation: Above test case has 4 sorted
arrays of size 4, 4, 4, 4
arr[][] = [[1, 2, 2, 2], [3, 3, 4, 4],
[5, 5, 6, 6]  [7, 8, 9, 9 ]]
The merged list will be 
[1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 
6, 6, 7, 8, 9, 9 ].

simple method:

create an output array of size n * k and then copy all the elements into the output array followed by sorting.

• Algorithm:
1. Create a output array of size n * k.
2. Traverse the matrix from start to end and insert all the elements in output array.
3. Sort and print the output array.

void mergeKArrays(int arr[][n], int a, int out[]) 
{ 
    int x=0; 
      
    //traverse the matrix 
    for(int i=0; i<a; i++) 
    { 
        for(int j=0; j<n ;j++) 
            out[x++]=arr[i][j]; 
    } 
      
    //sort the array 
    sort(out,out + n*a); 
      
} 

• Time Complexity :O(n*k*log(n*k)).
  since resulting array is of N*k size.
• Space Complexity :O(n*k), The output array is of size n*k.

An efficient solution is to use heap data structure. The time complexity of heap based solution is O(N Log k).

1. Create an output array.
2. Create a min heap of size k and insert 1st element in all the arrays into the heap
3. Repeat following steps while priority queue is not empty.
a) Remove minimum element from heap (minimum is always at root) and store it in output array.
b) Insert next element from the array from which the element is extracted. If the array doesn’t have any more elements, then do nothing.

typedef pair<int,pair<int,int>>pq;
int *mergeKArrays(int arr[][N], int k)
{
     int *res=new int[k*k];
     priority_queue<pq,vector<pq>,greater<pq>>q;
      for(int i=0;i<k;i++)
      {
          q.push(make_pair(arr[i][0],make_pair(i,0)));
      }
      int j=0;
     while(!q.empty())
     {
         
        pq curr=q.top();
         q.pop();
         res[j++]=curr.first;
         int iarr=curr.second.first;
         int iele=curr.second.second;
         if(iele < k-1)
         {
             q.push(make_pair(arr[iarr][iele+1], make_pair(iarr,iele+1) ));
             
         }
         
         
     }
     return res;
}

• Time Complexity :O( n * k * log k)
• Space Complexity :O(k)