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