fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class heap
  5. {
  6.     int cap;
  7.     int size;
  8.     int *arr;
  9. public:
  10.     heap(int cap)
  11.     {
  12.         this->cap=cap;
  13.         arr=new int[cap+1];
  14.         this->size=0;
  15.     }
  16.  
  17.     void insert(int key)
  18.     {
  19.         if (size == cap)
  20.             return;
  21.  
  22.         size++;
  23.         arr[size]=key;
  24.         percolate_up(size);
  25.     }
  26.  
  27.     void deleteMax()
  28.     {
  29.         if (size == 0)
  30.             return;
  31.  
  32.         arr[1]=arr[size];
  33.         size--;
  34.         int index=1;
  35.         while (true)
  36.         {
  37.             int left=2*index;
  38.             int right=2*index+1;
  39.             int l=index;
  40.             if(left<=size && arr[left]>arr[l])
  41.             {
  42.                 l=left;
  43.             }
  44.             if(right<=size && arr[right]>arr[l])
  45.             {
  46.                 l=right;
  47.             }
  48.  
  49.             if(l!=index)
  50.             {
  51.                 swap(arr[index],arr[l]);
  52.                 index=l;
  53.             }
  54.             else break;
  55.         };
  56.     }
  57.  
  58.     void percolate_up(int i)
  59.     {
  60.         while(i>1 && arr[i]>arr[i/2])
  61.         {
  62.             swap(arr[i],arr[i/2]);
  63.             i=i/2;
  64.         }
  65.  
  66.     }
  67.  
  68.     void print()
  69.     {
  70.         for(int i=1; i<=size; i++)
  71.         {
  72.             cout << arr[i] << "   ";
  73.         }
  74.         cout << endl;
  75.     }
  76. };
  77.  
  78. int main()
  79. {
  80.     heap h(10);
  81.     h.insert(1);
  82.     h.insert(2);
  83.     h.insert(3);
  84.     h.insert(4);
  85.     h.insert(5);
  86.     h.insert(6);
  87.     h.insert(7);
  88.     h.insert(8);
  89.     h.insert(9);
  90.     h.print();
  91.     h.deleteMax();
  92.     h.print();
  93. }
  94.  
  95.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
9   8   6   7   3   2   5   1   4   
8   7   6   4   3   2   5   1
https://ideone.com/fqHQgM
language:
C++ (gcc 8.3)
created:
4 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!