#include<bits/stdc++.h>
using namespace std;

class MinHeap{

    public:
    int *arr;
    int size{0};
    int capacity{1000};

    public:
    MinHeap(){
        arr = new int[capacity];
        size = 0;
    }
    ~MinHeap(){
        delete[] arr;
        arr = NULL;
        size = 0;
    }
    //know my parent and my children
    int leftchild(int node){
        int ans = 2*node + 1;
        return ans >= size? -1 : ans;
    }
    int rightchild(int node){
        int ans = 2*node + 2;
        return ans >= size? -1 : ans;
    }
    int parent(int node){
        return node ==0 ? -1 : (node-1)/2;
    }
    //heapify up
    void heapifyUp(int child_pos){
        int parent_pos = parent(child_pos);
        //base case
        if(child_pos ==0||parent_pos==-1 || arr[parent_pos] <arr[child_pos]){
            return;
        }
        swap(arr[parent_pos],arr[child_pos]);
        heapifyUp(parent_pos);
    }
    //push data
    void push(int node){
        assert(size + 1 <= capacity);
        arr[size++] = node;
        heapifyUp(size-1);
    }
    //pop data
    void heapifyDown(int parent_pos){
        int left_child = leftchild(parent_pos);
        int right_child = rightchild(parent_pos);

        int min_child = parent_pos;

        if(left_child!= -1 && arr[left_child] < arr[min_child]){
            min_child = left_child;
        }

        if(right_child!= -1 && arr[right_child] < arr[min_child]){
            min_child = right_child;
        }
        
        if(min_child!= parent_pos){
            swap(arr[parent_pos],arr[min_child]);
            heapifyDown(min_child);
        }

    }
    void pop(){
        assert(!isEmpty());
        swap(arr[0],arr[--size]);
        heapifyDown(0);
    }
    int top(){
        assert(!isEmpty());
        return arr[0];
    }
    bool isEmpty(){
        return size==0;
    }
};
int main(){
    MinHeap heap;
    heap.push(7);
    heap.push(1);
    heap.push(5);
    heap.push(2);
    heap.push(3);
	cout << "The heap traversal is : ";
    while (!heap.isEmpty()) {
        cout << heap.top() << " ";
        heap.pop();
    }
    return 0;
}