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

void printMinHeap(vector<int> arr) {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";    
    }
    cout << endl;
}

int getLeftChildIndex(int parentIndex) {
    return parentIndex * 2 + 1;
}

int getRightChildIndex(int parentIndex) {
    return parentIndex * 2 + 2;
}

int getParentIndex(int childIndex) {
    return  (childIndex - 1) / 2;
}

void heapifyUp(vector<int> &arr, int index) {
    int parentIndex = getParentIndex(index);
    while (parentIndex >= 0 && arr[index] < arr[parentIndex]) {
        swap(arr[parentIndex], arr[index]);
        index = parentIndex;
        parentIndex = getParentIndex(index);
    }
}

void heapifyDown(vector<int> &arr, int parentIndex) {
    int leftChildIndex = getLeftChildIndex(parentIndex);  
    int smallerChildIndex;    
    while (leftChildIndex < arr.size()) {
        // we need to find out which is smaller
        // left child or right child.
        smallerChildIndex = leftChildIndex;
        int rightChildIndex = getRightChildIndex(parentIndex);
        if (rightChildIndex < arr.size() &&
            arr[rightChildIndex] < arr[smallerChildIndex]) {
            smallerChildIndex = rightChildIndex;        
        }
        if (arr[parentIndex] < arr[smallerChildIndex]) {
            // this condition implies, min-heap integrity is
            // already maintained.    
            break;
        }
        swap(arr[parentIndex], arr[smallerChildIndex]);
        parentIndex = smallerChildIndex;
        leftChildIndex = getLeftChildIndex(parentIndex);
    }
}


void createMinHeap(vector<int> &arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapifyDown(arr, i);    
    }
}


void addElement(vector<int> &arr, int newEle) {
    arr.push_back(newEle);
    heapifyUp(arr, arr.size() - 1);
}


void removeElement(vector<int> &arr) {
    int n = arr.size();
    swap(arr[n - 1], arr[0]);
    arr.pop_back();
    heapifyDown(arr, 0);
}


int main() {
    vector<int> arr = {10, 22, 32, 6, 25, 22, 15, 56, 65, 72};
    createMinHeap(arr);
    printMinHeap(arr);
    addElement(arr, 8);
    printMinHeap(arr);
    removeElement(arr);
    printMinHeap(arr);
    removeElement(arr);
    printMinHeap(arr);
}