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