// C++ program to merge k sorted arrays of size n each.
#include<iostream>
#include<limits.h>
#include<bits/stdc++.h>
using namespace std;

#define n 4

class heap{
    int element;
    int i;
    int j;
    public:
        heap(int _element, int _i, int _j)
        {
            element=_element;
            i=_i;
            j=_j;
        }
        int getelement(){return element;}
        int geti() {return i;}
        int getj() {return j;}
};
class comparator{
public:    
bool operator()(heap h1, heap h2)
{
    return h1.getelement()>h2.getelement();
}
};
int *mergeKArrays(int a[][n], int k)
{
    priority_queue<heap, std::vector<heap>, comparator> pq;
	int *output = new int[n*k]; // To store output array
	int p,q,r;
	for(int i=0;i<k;i++)
    	{
    	    pq.push(heap(a[i][0],i,1));
    	    
    	}
	for(int count=0;count<n*k;count++)
    	{
    	    heap x = pq.top();
    	    output[count]= x.getelement();
    	    q=x.geti();
    	    r=x.getj();
    	    pq.pop();
    	    if(r<n)
        	    {
        	        
        	        p = a[x.geti()][x.getj()];
        	        r=x.getj()+1;
        	        
        	    }
    	    else
        	    {
        	        p = INT_MAX;
        	    }
        	        pq.push(heap(p,q,r));
    	    
    	}
	
	

	return output;
}



// A utility function to swap two elemen

// A utility function to print array elements
void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
	cout << arr[i] << " ";
}

// Driver program to test above functions
int main()
{
	// Change n at the top to change number of elements
	// in an array
	int arr[][n] = {{2, 6, 12, 34},
					{1, 9, 20, 1000},
					{23, 34, 90, 2000}};
	int k = sizeof(arr)/sizeof(arr[0]);

	int *output = mergeKArrays(arr, k);

	cout << "Merged array is " << endl;
	printArray(output, n*k);

	return 0;
}