Advertisement
prakharvk

merge k-sorted arrays using min-Heap

Jun 13th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> merge(vector<vector<int> >&v,int k){
  5.     vector<int>pointers(k,0);
  6.     vector<int>ans;
  7.     priority_queue<pair<int,int> >pq;
  8.     do{
  9.         pair<int,int> mini={INT_MAX,0};
  10.         for(int i=0;i<k;i++){
  11.             if(pointers[i]<v[i].size()){
  12.                 if(mini.first>v[i][pointers[i]]){
  13.                     mini={v[i][pointers[i]],i};
  14.                 }
  15.             }
  16.         }
  17.         if(!pq.empty()){
  18.             int num=pq.top().first;
  19.        
  20.             pq.pop();
  21.             ans.push_back(num);
  22.             // cout<<num<<" ";
  23.            
  24.         }
  25.         if(mini.first!=INT_MAX){
  26.             int index=mini.second;
  27.             pointers[index]++;
  28.             pq.push(mini);
  29.             // cout<<mini.first<<" "<<index<<endl;
  30.            
  31.         }
  32.    
  33.     }while(!pq.empty());
  34.     return ans;
  35. }
  36.  
  37. int main() {
  38.     int k;
  39.     cin>>k;
  40.     vector<vector<int> >v(k);
  41.     for(int i=0;i<k;i++){
  42.         vector<int>temp;
  43.         int n;
  44.         cin>>n;
  45.         for(int j=0;j<n;j++){
  46.             int c;
  47.             cin>>c;
  48.             temp.push_back(c);
  49.         }
  50.         v[i]=temp;
  51.        
  52.     }
  53.    
  54.     vector<int> ans=merge(v,k);
  55.     for(int i=0;i<ans.size();i++){
  56.         cout<<ans[i]<<" ";
  57.     }
  58.     // for(int i=0;i<k;i++){
  59.     //     for(int j=0;j<v[i].size();j++){
  60.     //         cout<<v[i][j]<<" ";
  61.     //     }
  62.     //     cout<<endl;
  63.     // }
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement