#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>


template <typename T,
                typename CompareFunc = decltype(std::less<T>()),
                        typename SwapFunc = decltype((void (*)(T&,T&))std::swap<T>) >
class Heap {
private:
    std::vector<T> heap;
    CompareFunc comparator;
    SwapFunc swap;

    void heapShiftDown (int it){
        int max = it;
        if (it * 2 + 1 < heap.size() && comparator(heap[max], heap[it * 2 + 1]))
            max = 2 * it + 1;
        if (it * 2 + 2 < heap.size() && comparator(heap[max], heap[it * 2 + 2]))
            max = 2 * it + 2;
        if (max != it){
            swap (heap[it], heap[max]);
            heapShiftDown(max);
        }
    }

    void heapShiftUp (int it){
        int parent = (it - 1) / 2;
        if (it && comparator(heap[parent], heap[it])){
            swap (heap[parent], heap[it]);
            heapShiftUp (parent);
        }
    }

public:
    Heap (CompareFunc cmp = std::less<T>(),
            SwapFunc swap = (void (*)(T&,T&))std::swap<T>) :
            comparator(cmp), swap(swap) {}

    void Insert (T value){
        heap.push_back(value);
        heapShiftUp(heap.size() - 1);
    }

    void Erase(int it){
        swap (heap[it], heap[heap.size() - 1]);
        heap.pop_back();

        if (it != heap.size()){
            heapShiftDown(it);
            heapShiftUp(it);
        }
    }

    T& operator[] (int it){
        return heap[it];
    }

    void Erase(){
        Erase(0);
    }

    T GetMax (){
        return heap[0];
    }

    int GetSize() {
        return heap.size();
    }
};

template <typename T, typename CompareFunc, typename SwapFunc>
Heap<T, CompareFunc, SwapFunc> BuildSpecialHeap (CompareFunc cmp, SwapFunc swap){
    return Heap<T,CompareFunc,SwapFunc>(cmp, swap);
}

template <typename Iterator> void heapSortSwap (Iterator& a, Iterator& b){
    std::swap (*a, *b);
}

template <typename Iterator, typename CompareFunc>
void heap_sort (Iterator begin, Iterator end, CompareFunc cmp){
    auto heap = BuildSpecialHeap<Iterator>(
            [&cmp] (Iterator a, Iterator b)  { return cmp (*a, *b); }
            , heapSortSwap<Iterator>);
    for (Iterator it = begin; it != end; it++)
        heap.Insert(it);
    while (heap.GetSize())
        heap.Erase();
}

int main(){
    Heap<int> x;
    x.Insert(5);
    x.Insert(6);
    x.Insert(3);
    std::cout << x.GetMax() << std::endl;
    x.Erase();
    std::cout << x.GetMax() << std::endl;

    // ----------------------------------------------
    std::cout << std::endl << std::endl;
    // ----------------------------------------------

    std::vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(2);
    v.push_back(6);
    v.push_back(7);
    v.push_back(5);
    heap_sort(v.begin(), v.end(), std::less<int>());
    for (int i = 0; i < v.size(); i++)
        std::cout << v[i] << " \n";
    return 0;
}