fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class MinHeap {
  5. public:
  6.     int *arr;
  7.     int size{0};
  8.     int capacity{1000};
  9.  
  10.     MinHeap() {
  11.         arr = new int[capacity];
  12.         size = 0;
  13.     }
  14.  
  15.     ~MinHeap() {
  16.         delete[] arr;
  17.         arr = nullptr;
  18.         size = 0;
  19.     }
  20.  
  21.     int leftchild(int node) {
  22.         int ans = 2 * node + 1;
  23.         return ans >= size ? -1 : ans;
  24.     }
  25.  
  26.     int rightchild(int node) {
  27.         int ans = 2 * node + 2;
  28.         return ans >= size ? -1 : ans;
  29.     }
  30.  
  31.     int parent(int node) {
  32.         return node == 0 ? -1 : (node - 1) / 2;
  33.     }
  34.  
  35.     void heapifyUp(int child_pos) {
  36.         int parent_pos = parent(child_pos);
  37.         if (child_pos == 0 || parent_pos == -1 || arr[parent_pos] < arr[child_pos]) {
  38.             return;
  39.         }
  40.         swap(arr[parent_pos], arr[child_pos]);
  41.         heapifyUp(parent_pos);
  42.     }
  43.  
  44.     void push(int node) {
  45.         assert(!isFull());
  46.         arr[size++] = node;
  47.         heapifyUp(size - 1);
  48.     }
  49.  
  50.     void heapifyDown(int parent_pos) {
  51.         int left_child = leftchild(parent_pos);
  52.         int right_child = rightchild(parent_pos);
  53.         int min_child = parent_pos;
  54.  
  55.         if (left_child != -1 && arr[left_child] < arr[min_child]) {
  56.             min_child = left_child;
  57.         }
  58.  
  59.         if (right_child != -1 && arr[right_child] < arr[min_child]) {
  60.             min_child = right_child;
  61.         }
  62.  
  63.         if (min_child != parent_pos) {
  64.             swap(arr[parent_pos], arr[min_child]);
  65.             heapifyDown(min_child);
  66.         }
  67.     }
  68.  
  69.     void pop() {
  70.         assert(!isEmpty());
  71.         swap(arr[0], arr[--size]);
  72.         heapifyDown(0);
  73.     }
  74.  
  75.     int top() {
  76.         assert(!isEmpty());
  77.         return arr[0];
  78.     }
  79.  
  80.     bool isEmpty() {
  81.         return size == 0;
  82.     }
  83.  
  84.     bool isFull() {
  85.         return size == capacity;
  86.     }
  87.  
  88. };
  89. class MaxHeaphw{
  90.     private:
  91.     MinHeap minheap;
  92.     public:
  93.     MaxHeaphw()=default;
  94.     MaxHeaphw(const vector<int> &v){
  95.         for(auto &x:v){
  96.             minheap.push(-x);
  97.         }
  98.     }
  99.     bool empty(){
  100.         return minheap.isEmpty();
  101.     }
  102.     int top(){
  103.         return -minheap.top();
  104.     }
  105.     void pop(){
  106.         minheap.pop();
  107.     }
  108.     void push(int value){
  109.         minheap.push(-value);
  110.     }
  111.     bool isEmpty(){
  112.         return minheap.isEmpty();
  113.     }
  114.     bool isFull(){
  115.         return minheap.isFull();
  116.     }
  117.     int Size(){
  118.         return minheap.size;
  119.     }
  120.  
  121. };
  122. class kthsmallest{
  123.     private:
  124.     int k;
  125.     MaxHeaphw mh;
  126.     public:
  127.  
  128.     kthsmallest(int k){
  129.         this->k = k;
  130.     }
  131.     int next(int number){
  132.         if(mh.Size()<k){
  133.             mh.push(number);
  134.         }
  135.         else if(number<mh.top()){
  136.             mh.pop();
  137.             mh.push(number);
  138.         }
  139.         return mh.top();
  140.     }
  141.  
  142. };
  143.  
  144. int main(){
  145.     kthsmallest k(4);
  146.     int number;
  147.     while(cin >> number){
  148.         if(number ==-1)  break;
  149.         cout <<"answer : "<<k.next(number)<<endl;
  150.     }
  151.     return 0;
  152. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
 9 8 7 6 5 4 10 8 3 5 15 -1
stdout
copy 
answer : 9
answer : 9
answer : 9
answer : 9
answer : 8
answer : 7
answer : 7
answer : 7
answer : 6
answer : 5
answer : 5
https://ideone.com/GwvLM9
language:
C++ (gcc 8.3)
created:
7 days 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!