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.     //Time O(log n)
  45.     void push(int node){
  46.         assert(!isFull());
  47.         arr[size++] = node;
  48.         heapifyUp(size-1);
  49.     }
  50.     //pop data
  51.     void heapifyDown(int parent_pos){
  52.         int left_child = leftchild(parent_pos);
  53.         int right_child = rightchild(parent_pos);
  54.  
  55.         int min_child = parent_pos;
  56.  
  57.         if(left_child!= -1 && arr[left_child] < arr[min_child]){
  58.             min_child = left_child;
  59.         }
  60.  
  61.         if(right_child!= -1 && arr[right_child] < arr[min_child]){
  62.             min_child = right_child;
  63.         }
  64.  
  65.         if(min_child!= parent_pos){
  66.             swap(arr[parent_pos],arr[min_child]);
  67.             heapifyDown(min_child);
  68.         }
  69.  
  70.     }
  71.     //Time O(log n)
  72.     void pop(){
  73.         assert(!isEmpty());
  74.         swap(arr[0],arr[--size]);
  75.         heapifyDown(0);
  76.     }
  77.     int top(){
  78.         assert(!isEmpty());
  79.         return arr[0];
  80.     }
  81.     bool isEmpty(){
  82.         return size==0;
  83.     }
  84.     bool isFull(){
  85.         return size==capacity;
  86.     }
  87.  
  88.  
  89. };
  90. class MinHeap2 :public MinHeap{
  91.     public:
  92.     int size{};
  93.     int capacity{1000};
  94.     int *arr;
  95.     //floyed approach
  96.     MinHeap2(vector<int> &v){
  97.         arr = new int[capacity];
  98.         size = v.size();
  99.         //O(n)
  100.         for(int i=0;i<size;i++){
  101.             arr[i] = v[i];
  102.         }
  103.         //O(n)
  104.         //the position size/2 -1 is the first non leaf node
  105.         for(int i=size/2-1;i>=0;i--){
  106.             heapifyDown(i);
  107.         }
  108.     }
  109.     void test_mx_heap(){
  110.         priority_queue<int>mx_heap;
  111.         //// will be mn heap ////
  112.         /*
  113.         priority_queue<int,vector<int>,greater<int>>mn_heap;
  114.         */
  115.         mx_heap.push(1);
  116.         mx_heap.push(2);
  117.         mx_heap.push(10);
  118.         mx_heap.push(4);
  119.         mx_heap.push(6);
  120.         while(!mx_heap.empty()){
  121.             cout << mx_heap.top() << " ";
  122.             mx_heap.top();
  123.         }
  124.         cout <<'\n';
  125.     }
  126. };
  127. int main(){
  128.     MinHeap heap;
  129.     heap.push(7);
  130.     heap.push(1);
  131.     heap.push(5);
  132.     heap.push(2);
  133.     heap.push(3);
  134.  
  135.     //O(nlogn)
  136.     cout <<"The heap traversal is\n";
  137.     while (!heap.isEmpty()) {
  138.         cout << heap.top() << " ";
  139.         heap.pop();
  140.     }
  141.     return 0;
  142. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The heap traversal is
1 2 3 5 7
https://ideone.com/NMuvQy
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!