# Merge K Sorted Arrays and Print Sorted Output

Given k sorted arrays of size n each, write a program to merge those arrays and prints the sorted output

### Example

INPUT :
arr[][] = {{1,5,7},{2,4,6},{3,10,13}}

OUTPUT :
{1,2,3,4,5,6,10,13}

Time Complexity : O(nklogk)

where k is the number of sorted arrays and n is the size of the array
In this method the main idea is using minheap

## Algorithm

1. Create an output array of size n*k

2. Create a min heap of size k and insert first element in all the arrays into the min heap

3. Initialize count = 0 and till count less than n*k.

1. Get the minimum element from heap(ie, root) and store it in output array ie,output[count]
2. Replace heap root with next element from the array from which the element is extracted. If the array doesnâ€™t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

4. Print the output array.

## C++ Program

```#include<iostream>
#include<limits.h>
#define n 3
using namespace std;

// A min heap node
struct MinHeapNode
{
int element; // The element to be stored
int i; // index of the array from which the element is taken
int j; // index of the next element to be picked from array
};

// Prototype of a utility function to swap two min heap nodes
void swap(MinHeapNode *x, MinHeapNode *y);

// A class for Min Heap
class MinHeap
{
MinHeapNode *harr; // pointer to array of elements in heap
int heap_size; // size of min heap
public:
// Constructor: creates a min heap of given size
MinHeap(MinHeapNode a[], int size);

// to heapify a subtree with root at given index
void MinHeapify(int );

// to get index of left child of node at index i
int left(int i) { return (2*i + 1); }

// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }

// to get the root
MinHeapNode getMin() { return harr[0]; }

// to replace root with new node x and heapify() new root
void replaceMin(MinHeapNode x) { harr[0] = x;  MinHeapify(0); }
};

// This function takes an array of arrays as an argument and
// All arrays are assumed to be sorted. It merges them together
// and prints the final sorted output.
int *mergeKSortedArrays(int arr[][n], int k)
{
int *output = new int[n*k];  // To store output array

// Create a min heap with k heap nodes.  Every heap node
// has first element of an array
MinHeapNode *harr = new MinHeapNode[k];
for (int i = 0; i < k; i++)
{
harr[i].element = arr[i][0]; // Store the first element
harr[i].i = i;  // index of array
harr[i].j = 1;  // Index of next element to be stored from array
}
MinHeap hp(harr, k); // Create the heap

// Now one by one get the minimum element from min
// heap and replace it with next element of its array
for (int count = 0; count < n*k; count++)
{
// Get the minimum element and store it in output
MinHeapNode root = hp.getMin();
output[count] = root.element;

// Find the next element that will replace current
// root of heap. The next element belongs to same
// array as the current root.
if (root.j < n)
{
root.element = arr[root.i][root.j];
root.j += 1;
}
// If root was the last element of its array
else root.element =  INT_MAX; //INT_MAX is for infinite

// Replace root with next element of array
hp.replaceMin(root);
}

return output;
}

// Standard Min Heap Methods
// Constructor: Builds a heap from a given array a[] of given size
MinHeap::MinHeap(MinHeapNode a[], int size)
{
heap_size = size;
harr = a;  // store address of array
int i = (heap_size - 1)/2;
while (i >= 0)
{
MinHeapify(i);
i--;
}
}

// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l].element < harr[i].element)
smallest = l;
if (r < heap_size && harr[r].element < harr[smallest].element)
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}

// A utility function to swap two elements
void swap(MinHeapNode *x, MinHeapNode *y)
{
MinHeapNode temp = *x;  *x = *y;  *y = temp;
}

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

int main()
{
// Change n at the top to change number of elements
// in an array
int arr[][n] = {{1,5,7},{2,4,6},{3,10,13}} ;
int k = sizeof(arr)/sizeof(arr[0]);

int *output = mergeKSortedArrays(arr, k);

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

return 0;
}```

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup