fork download
copy 
  1. // C++ program to merge k sorted arrays of size n each.
  2. #include<iostream>
  3. #include<limits.h>
  4. using namespace std;
  5.  
  6. #define n 4
  7.  
  8. // A min heap node
  9. struct MinHeapNode
  10. {
  11.     int element; // The element to be stored
  12.     int i; // index of the array from which the element is taken
  13.     int j; // index of the next element to be picked from array
  14. };
  15.  
  16. // Prototype of a utility function to swap two min heap nodes
  17. void swap(MinHeapNode *x, MinHeapNode *y);
  18.  
  19. // A class for Min Heap
  20. class MinHeap
  21. {
  22.     MinHeapNode *harr; // pointer to array of elements in heap
  23.     int heap_size; // size of min heap
  24. public:
  25.     // Constructor: creates a min heap of given size
  26.     MinHeap(MinHeapNode a[], int size);
  27.  
  28.     // to heapify a subtree with root at given index
  29.     void MinHeapify(int );
  30.  
  31.     // to get index of left child of node at index i
  32.     int left(int i) { return (2*i + 1); }
  33.  
  34.     // to get index of right child of node at index i
  35.     int right(int i) { return (2*i + 2); }
  36.  
  37.     // to get the root
  38.     MinHeapNode getMin() { return harr[0]; }
  39.  
  40.     // to replace root with new node x and heapify() new root
  41.     void replaceMin(MinHeapNode x) { harr[0] = x;  MinHeapify(0); }
  42. };
  43.  
  44. // This function takes an array of arrays as an argument and
  45. // All arrays are assumed to be sorted. It merges them together
  46. // and prints the final sorted output.
  47. int *mergeKArrays(int arr[][n], int k)
  48. {
  49.     int *output = new int[n*k];  // To store output array
  50.  
  51.     // Create a min heap with k heap nodes.  Every heap node
  52.     // has first element of an array
  53.     MinHeapNode *harr = new MinHeapNode[k];
  54.     for (int i = 0; i < k; i++)
  55.     {
  56.         harr[i].element = arr[i][0]; // Store the first element
  57.         harr[i].i = i;  // index of array
  58.         harr[i].j = 1;  // Index of next element to be stored from array
  59.     }
  60.     MinHeap hp(harr, k); // Create the heap
  61.  
  62.     // Now one by one get the minimum element from min
  63.     // heap and replace it with next element of its array
  64.     for (int count = 0; count < n*k; count++)
  65.     {
  66.         // Get the minimum element and store it in output
  67.         MinHeapNode root = hp.getMin();
  68.         output[count] = root.element;
  69.  
  70.         // Find the next elelement that will replace current
  71.         // root of heap. The next element belongs to same
  72.         // array as the current root.
  73.         if (root.j < n)
  74.         {
  75.             root.element = arr[root.i][root.j];
  76.             root.j += 1;
  77.         }
  78.         // If root was the last element of its array
  79.         else root.element =  INT_MAX; //INT_MAX is for infinite
  80.  
  81.         // Replace root with next element of array
  82.         hp.replaceMin(root);
  83.     }
  84.  
  85.     return output;
  86. }
  87.  
  88. // FOLLOWING ARE IMPLEMENTATIONS OF STANDARD MIN HEAP METHODS
  89. // FROM CORMEN BOOK
  90. // Constructor: Builds a heap from a given array a[] of given size
  91. MinHeap::MinHeap(MinHeapNode a[], int size)
  92. {
  93.     heap_size = size;
  94.     harr = a;  // store address of array
  95.     int i = (heap_size - 1)/2;
  96.     while (i >= 0)
  97.     {
  98.         MinHeapify(i);
  99.         i--;
  100.     }
  101. }
  102.  
  103. // A recursive method to heapify a subtree with root at given index
  104. // This method assumes that the subtrees are already heapified
  105. void MinHeap::MinHeapify(int i)
  106. {
  107.     int l = left(i);
  108.     int r = right(i);
  109.     int smallest = i;
  110.     if (l < heap_size && harr[l].element < harr[i].element)
  111.         smallest = l;
  112.     if (r < heap_size && harr[r].element < harr[smallest].element)
  113.         smallest = r;
  114.     if (smallest != i)
  115.     {
  116.         swap(&harr[i], &harr[smallest]);
  117.         MinHeapify(smallest);
  118.     }
  119. }
  120.  
  121. // A utility function to swap two elements
  122. void swap(MinHeapNode *x, MinHeapNode *y)
  123. {
  124.     MinHeapNode temp = *x;  *x = *y;  *y = temp;
  125. }
  126.  
  127. // A utility function to print array elements
  128. void printArray(int arr[], int size)
  129. {
  130.    for (int i=0; i < size; i++)
  131.        cout << arr[i] << " ";
  132. }
  133.  
  134. // Driver program to test above functions
  135. int main()
  136. {
  137.     // Change n at the top to change number of elements
  138.     // in an array
  139.     int arr[][n] =  {{2, 6, 12, 34},
  140.                      {1, 9, 20, 1000},
  141.                      {23, 34, 90, 2000}};
  142.     int k = sizeof(arr)/sizeof(arr[0]);
  143.  
  144.     int *output = mergeKArrays(arr, k);
  145.  
  146.     cout << "Merged array is " << endl;
  147.     printArray(output, n*k);
  148.  
  149.     return 0;
  150. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Merged array is 
1 2 6 9 12 20 23 34 34 90 1000 2000
https://ideone.com/RlDcFC
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!