fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class MaxHeap{
  5.     private:
  6.     int size{};
  7.     int capacity{1000};
  8.     int *arr{};
  9.     public:
  10.     MaxHeap(){
  11.         arr = new int[capacity];
  12.         size =0;
  13.     }
  14.     ~MaxHeap(){
  15.         delete[] arr;
  16.     }
  17.     int leftchild(int node){
  18.         int ans = 2*node + 1;
  19.         return ans >= size? -1 : ans;
  20.     }
  21.     int rightchild(int node){
  22.         int ans = 2*node + 2;
  23.         return ans >= size? -1 : ans;
  24.     }
  25.     int parent(int node){
  26.         return node ==0 ? -1 : (node-1)/2;
  27.     }
  28.     void heapifyUp(int child_pos){
  29.         int parent_pos = parent(child_pos);
  30.         //base case
  31.         if(child_pos ==0||parent_pos==-1 || arr[parent_pos] >arr[child_pos]){
  32.             return;
  33.         }
  34.         swap(arr[parent_pos],arr[child_pos]);
  35.         heapifyUp(parent_pos);
  36.     }
  37.     bool isFull(){
  38.         return size == capacity;
  39.     }
  40.     bool isEmpty(){
  41.         return size == 0;
  42.     }
  43.     void push(int node){
  44.         assert(!isFull());
  45.         arr[size] = node;
  46.         size++;
  47.         heapifyUp(size-1);
  48.     }
  49.     void heapifyDown(int parent_pos){
  50.         int left_child = leftchild(parent_pos);
  51.         int right_child = rightchild(parent_pos);
  52.  
  53.         int max_child = parent_pos;
  54.  
  55.         if(left_child!= -1 && arr[left_child] > arr[max_child]){
  56.             max_child = left_child;
  57.         }
  58.  
  59.         if(right_child!= -1 && arr[right_child] > arr[max_child]){
  60.             max_child = right_child;
  61.         }
  62.  
  63.         if(max_child!= parent_pos){
  64.             swap(arr[parent_pos],arr[max_child]);
  65.             heapifyDown(max_child);
  66.         }
  67.     }
  68.     void pop(){
  69.         assert(!isEmpty());
  70.         swap(arr[0],arr[--size]);
  71.         heapifyDown(0);
  72.     }
  73.     int top(){
  74.         assert(!isEmpty());
  75.         return arr[0];
  76.     }
  77. };
  78. int main(){
  79.     MaxHeap heap;
  80.     heap.push(3);
  81.     heap.push(5);
  82.     heap.push(8);
  83.     cout << "Max heap traversal is : \n";
  84.     while(!heap.isEmpty()){
  85.         cout << heap.top() << " ";
  86.         heap.pop();
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max heap traversal is : 
8 5 3
https://ideone.com/AUsaRg
language:
C++ (gcc 8.3)
created:
10 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!