#ifndef HEAP_H
#define HEAP_H
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
class Heap
{
public:
    Heap(vector<T> &_vec) : vec(_vec){}
    ~Heap(){
        vec.~vector();
    }
    Heap(const Heap& rhs)
    {
        this->vec = rhs.vec;
    }
    Heap &operator =(const Heap&rhs)
    {
         if(this == &rhs) return *this;
         vec.clear();
         this->vec = rhs.vec;
         return *this;
    }
    void heapify(bool isMax,int index,int size)
    {
        int l = left(index);
        int r = right(index);
        int largest;
        if(isMax)
        {
            if(l < size && vec.at(l) > vec.at(index))
                largest = l;
            else largest = index;
            if(r < size && vec.at(r) > vec.at(largest))
                largest = r;
            if(largest != index)
            {
                std::swap(vec.at(index),vec.at(largest));
                heapify(true,largest,size);
            }
        }
        else
        {
            if(l < size && vec.at(l) < vec.at(index))
                largest = l;
            else largest = index;
            if(r < size && vec.at(r) < vec.at(largest))
                largest = r;
            if(largest != index)
            {
                std::swap(vec.at(index),vec.at(largest));
                heapify(false,largest,size);
            }
        }
    }
    void build_heapify(bool isMax,int size)
    {
        int _size = size;
        for(int i=_size/2;i>=0;i--)
                heapify(isMax,i,size);
    }
    void sort(bool isMax)
    {
        int size = vec.size()-1;
        build_heapify(isMax,size);
        for(int i=size;i>=0;i--)
        {
            std::swap(vec.at(0),vec.at(i));
            int _size = i;
            heapify(isMax,0,_size);
        }
    }
    friend ostream& operator <<(ostream &os,
                                const Heap<T> &heap)
    {
        for(int i=0;i<heap.vec.size();i++)
        {
            os << heap.vec.at(i) << ends;
        }
        os << endl;
        return os;
    }
    T &operator[](size_t n)
    {
        return vec[n];
    }
private:
    inline int left(int index)
    {
        return index*2+1;
    }
    inline int right(int index)
    {
        return index*2+2;
    }

    vector<T> &vec;
};


#endif // HEAP_H