fork download
copy 
  1. // of size n each. 
  2. #include <bits/stdc++.h> 
  3.  
  4. using namespace std; 
  5.  
  6.  
  7. // A pair of pairs, first element is going to 
  8. // store value, second element index of array 
  9. // and third element index in the array. 
  10.  
  11. typedef pair<int, pair<int, int> > ppi; 
  12.  
  13.  
  14. // This function takes an array of arrays as an 
  15. // argument and all arrays are assumed to be 
  16. // sorted. It merges them together and prints 
  17. // the final sorted output. 
  18.  
  19. vector<int> mergeKArrays(vector<vector<int> > arr) 
  20. { 
  21.  
  22.     vector<int> output; 
  23.  
  24.  
  25.  
  26.     // Create a min heap with k heap nodes. Every 
  27.  
  28.     // heap node has first element of an array 
  29.  
  30.     priority_queue<ppi, vector<ppi>, greater<ppi> > pq; 
  31.  
  32.  
  33.  
  34.     for (int i = 0; i < arr.size(); i++) 
  35.  
  36.         pq.push({ arr[i][0], { i, 0 } }); 
  37.  
  38.  
  39.  
  40.     // Now one by one get the minimum element 
  41.  
  42.     // from min heap and replace it with next 
  43.  
  44.     // element of its array 
  45.  
  46.     while (pq.empty() == false) { 
  47.  
  48.         ppi curr = pq.top(); 
  49.  
  50.         pq.pop(); 
  51.  
  52.  
  53.  
  54.         // i ==> Array Number 
  55.  
  56.         // j ==> Index in the array number         
  57.  
  58.         int i = curr.second.first;   
  59.  
  60.         int j = curr.second.second;  
  61.  
  62.  
  63.  
  64.         output.push_back(curr.first); 
  65.  
  66.  
  67.  
  68.         // The next element belongs to same array as  
  69.  
  70.         // current. 
  71.  
  72.         if (j + 1 < arr[i].size()) 
  73.  
  74.             pq.push({ arr[i][j + 1], { i, j + 1 } }); 
  75.  
  76.     } 
  77.  
  78.  
  79.  
  80.     return output; 
  81. } 
  82.  
  83.  
  84. // Driver program to test above functions 
  85.  
  86. int main() 
  87. { 
  88.  
  89.     // Change n at the top to change number 
  90.  
  91.     // of elements in an array 
  92.  
  93.     vector<vector<int> > arr{ { 2, 6, 12 }, 
  94.  
  95.                               { 1, 9 }, 
  96.  
  97.                               { 23, 34, 90, 2000 } }; 
  98.  
  99.  
  100.  
  101.     vector<int> output = mergeKArrays(arr); 
  102.  
  103.  
  104.  
  105.     cout << "Merged array is " << endl; 
  106.  
  107.     for (auto x : output) 
  108.  
  109.         cout << x << " "; 
  110.  
  111.  
  112.  
  113.     return 0; 
  114. }
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Merged array is 
1 2 6 9 12 23 34 90 2000
https://ideone.com/xjoG3t
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!