# 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:**- Create a output array of size n * k.
- Traverse the matrix from start to end and insert all the elements in output array.
- 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.

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)