#include 
#include 
#include 
#include 
#include 

using namespace std; //Not the best tactic, used for cleaner code and better understanding

class Heap {
private:
std::vector heap;
int hpsz;
public:

Heap(){
        hpsz=0; //At first the Heap is Empty
        heap.push_back(0);  //Index 0 must be initialized because we start indexing from 1
}

Heap(std::vector& array){
        int n = array.size();
        heap.push_back(100);  //The first index of heap array is 1 so we must fill 0 index with dummy content let it be 0
        heap.insert(heap.end(),array.begin(),array.end());  //  0
        hpsz=n; //Heap size = Heap Array size
        for (int i = n / 2; i > 0; i--) combine(i);
}

void insert(int elmnt) {
        heap.push_back(elmnt);
        hpsz++;
        int i = hpsz, parent = i / 2;
        while ((i > 1) && (heap[parent] < heap[i]))
        {
                iter_swap(heap.begin() + parent, heap.begin() + i);
                i = parent; parent = i / 2;
        }
}

//Get max without deleting from heap
int peek_max(){
        return heap[1];
}

void combine (int i){
        int mp=i,left=2*i,right=(2*i)+1;
        if((leftheap[mp])) {
                mp = left;
        }
        if((rightheap[mp])) {
                mp = right;
        }
        if(mp!=i) {
                iter_swap(heap.begin() + i, heap.begin() + mp);
                combine(mp);
        }
}

int deletemax(){
        if(isEmpty()) return -1;
        int max = heap[1];

        heap[1] = heap[hpsz--];
        combine(1);
        return max;
}

bool isEmpty(){
        return (hpsz==0);
}

int getHeapSize(){
        return (hpsz);
}

void heapSort(){
        int temp = hpsz;
        for (int i = hpsz; i > 1; i--)  {
                iter_swap(heap.begin() + 1, heap.begin() + i);
                hpsz--;
                combine(1);
        }
        hpsz = temp;
}

void printHeap(){
        for (int i = 1; i