#pragma once
#include<iostream>
using namespace std;
#include<vector>

template<class T>    //仿函数
struct Less
{
    bool operator()(const T&l, const T&r)  //重载括号
    {
        return l < r;
    }
};

template<class T>
struct Greater
{
    bool operator()(const T&l, const T&r)
    {
        return l>r;
    }
};

template<class T,class Compare=Greater<T>>
class Heap
{
public:
    Heap()
    {}

    Heap(const T* a, size_t size)   //建堆
    {
        for (int i = 0; i < size; ++i)      //先将数据push进vector中
        {
            _a.push_back(a[i]);
        }

        for (int j = (_a.size() - 2) / 2; j > 0; j--)  //从非叶子节点开始，向下调整
        {
            AdjustDown(j);
        }
    }

    bool Isempty()   //判空
    {
        return _a.empty();
    }

    T& top()    //取栈顶元素
    {
        if (!_a.empty())
        return _a[0];
    }

    void Pop()   //在树中删除节点
    {
        if (_a.empty())
            return;

//交换第一个节点与最后一个节点的值，删除最后一个节点，然后向下调整
        swap(_a[0], _a[_a.size() - 1]);  
        _a.pop_back();
        if (!_a.empty())
            AdjustDown(0);
    }

    void Push(const T& x)    //在树中插入节点
    {
        _a.push_back(x);
        if (!_a.empty())
            AdjustUp(_a.size() - 1);   //向上调整最后一个节点
    }
protected:
    void AdjustUp(int child)    //向上调整
    {    
        while (child > 0)
        {
            Compare com;
            int parent = (child - 1) / 2;
            if (com(_a[parent] , _a[child]))
            {
                swap(_a[parent], _a[child]);
                child = parent;
            }    
            else
            {
                break;
            }
        }
    }

    void AdjustDown(int root)   //小堆，子节点大于父节点
    {
        int parent = root;
        int child = parent * 2 + 1;   //先为左节点
        while (child+1<_a.size())
        {
            Compare com;
            if (_a[child + 1]>_a[child])   //找出孩子节点中较大的那个数
                ++child;

            if (child<_a.size()&&com(_a[parent] , _a[child]))   //比较父节点与孩子节点的大小然后作出相应的处理
            {
                swap(_a[parent], _a[child]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
private:
    vector<T>  _a;
};

Heap堆