fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void minHeapify(vector<int> &vec, int i, int& n){
  5.     int smallest = i;
  6.     int left = 2 * i + 1, right = left + 1;
  7.  
  8.     if(left < n && vec[left] < vec[smallest])
  9.         smallest = left;
  10.  
  11.     if(right < n && vec[right] < vec[smallest])
  12.         smallest = right;
  13.  
  14.     if(smallest ^ i){
  15.         swap(vec[i], vec[smallest]);
  16.         minHeapify(vec, smallest, n);
  17.     }
  18. }
  19.  
  20. int main()
  21. {
  22.     int k, val, heapSize = 0; cin>>k;
  23.  
  24.     vector<int> vec;
  25.  
  26.     while(true){
  27.         cin>>val;
  28.  
  29.         if(val == -1)
  30.             break;
  31.  
  32.         if(heapSize < k){
  33.             vec.push_back(val);
  34.             ++heapSize;
  35.         }
  36.         else if(val > vec[0]){
  37. 	        vec[0] = val;
  38.         }
  39.  
  40.         minHeapify(vec, 0, heapSize);
  41.  
  42.         if(heapSize == k)
  43.             cout<<vec[0]<<" ";
  44.         else
  45.             cout<<"N ";
  46.     }
  47.  
  48.     cout<<"\nThe elements in the heap:\n";
  49.     for(auto &val: vec)
  50.     	cout<<val<<" ";
  51.  
  52.     return 0;
  53. }
Success #stdin #stdout 0s 4340KB
comments (?)
stdin 
3
10 20 11 70 50 40 100 5
-1
stdout 
N N 10 11 20 40 50 50 
The elements in the heap:
50 100 70
https://ideone.com/yfsUSu
K largest element in a stream using heaps
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!