#include <iostream>
#include <cstdio>
#include <vector>
#include <iostream>
#include <climits>

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

class Heap {
private:
std::vector<int> 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<int>& 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((left<=hpsz) && (heap[left]>heap[mp])) {
                mp = left;
        }
        if((right<=hpsz) && (heap[right]>heap[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 <= hpsz; i++) {
                printf("%d ", heap[i] );
        }
        printf("\n");
}
};

int main(){
        /*
           Heap can be constructed using vector as input
         */
        int a[] = {3,4,10,8,15,16,17,12,11,20};
        vector<int> heapin (a, a + sizeof(a) / sizeof(a[0]) ); //C++2003
        //std::vector<int> heapin ({3,4,10,8,15,16,17,12,11,20}); //C++2011
        // std::vector<int> heapin(std::begin(a), std::end(a));    //C++2003
        Heap test(heapin);
        /*
           Heap can be constructed using one by one insertion of elements
           <-------------------------------------------------------------->
           Heap test;
           int num_elements;
           printf("Enter number of elements\n");
           scanf("%d\n",&num_elements);
           int elem;

           while(num_elements!=0) {
                  num_elements--;
                  scanf("%dendl",&elem );
                  test.insert(elem);
           }
         */

        test.printHeap(); //Heap array
        test.heapSort();  //after heap sorting the array does not include a list
        test.printHeap(); //Sorted array

        /*
         * Use the following loop to extract all the elements from head of max heap
           while (!test.isEmpty()) {
                printf("Max after delete: %d\n", test.deletemax());
           }
         */



}