fork download
copy 
  1. // author - shreyanshjn
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. class Heap {
  6. private:
  7.     vector<int> arr;
  8. public:
  9.     int getRightChild(int i) {
  10.         return i * 2 + 2;
  11.     }
  12.     int getLeftChild(int i) {
  13.         return i * 2 + 1;
  14.     }
  15.     int getPar(int i) {
  16.         return (i - 1) / 2;
  17.     }
  18.     bool hasRightChild(int i) {
  19.         return i * 2 + 2 < (int)arr.size();
  20.     }
  21.     bool hasLeftChild(int i) {
  22.         return i * 2 + 1 < (int)arr.size();
  23.     }
  24.     int top() {
  25.         return arr[0];
  26.     }
  27.     void push(int x) {
  28.         arr.push_back(x);
  29.         heapifyUp();
  30.     }
  31.     void pop() {
  32.         int index = arr.size() - 1;
  33.         swap(arr[0], arr[index]);
  34.         arr.pop_back();
  35.         heapifyDown();
  36.     }
  37.     void heapifyUp() {
  38.         int index = arr.size() - 1;
  39.         int par = (index - 1) / 2;
  40.         while(par >= 0 and arr[index] > arr[par]) {
  41.         	swap(arr[index], arr[par]);
  42.         	index = par;
  43.         	par = (index - 1) / 2;
  44.         }
  45.     }
  46.     void heapifyDown() {
  47.         int index = 0;
  48.         while(hasLeftChild(index)) {
  49.             int greater = getLeftChild(index);
  50.             if(hasRightChild(index) and arr[getRightChild(index)] > arr[greater]) {
  51.                 greater = getRightChild(index);
  52.             }
  53.             if(arr[index] > arr[greater]) {
  54.                 break;
  55.             }
  56.             else {
  57.                 swap(arr[index], arr[greater]);
  58.             }
  59.             index = greater;
  60.         }
  61.     }
  62. };
  63.  
  64. int main() {
  65.     int n; cin >> n;
  66.     Heap h;
  67.     for(int i = 0; i < n; i++) {
  68.         string str; cin >> str;
  69.         if(str == "push") {
  70.             int a; cin >> a;
  71.             h.push(a);
  72.         }
  73.         else if(str == "pop") {
  74.             h.pop();
  75.         }
  76.         else if(str == "top") {
  77.             cout << h.top() << endl;
  78.         }
  79.     }
  80. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
push 10
push 15
top
pop
top
stdout
copy 
15
10
https://ideone.com/ASvYwr
implement priority queue using heap
language:
C++14 (gcc 8.3)
created:
5 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!