#pragma once
#include <vector>

// 小于的仿函数
template <class T>
struct Less
{
    bool operator() (const T &val1, const T &val2)
    {
        return val1 < val2;
    }
};
// 大于的仿函数，
template <class T>
struct Greater
{
    bool operator()(const T &val1, const T &val2)
    {
        return val1 > val2;
    }
};

template <class T, class Container = std::vector<T>, class Compare = Greater<T>>
class priority_queue
{
private:
    Container _c;
    Compare _com;

public:
    // 向上调堆，发生push操作时元素加到最后一个位置
    void shiftUp(int child)
    {
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            // 假设选用Greater，当parent > child 时交换，即结果为升序，对应为小根堆
            if (_com(_c[parent], _c[child]))
            {
                std::swap(_c[parent], _c[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
                break;
        }
    }

    // 向下调堆，发生pop则交换首尾元素然后删除尾元素
    void shiftDown(int parent)
    {
        int child = 2 * parent + 1;
        while (child < _c.size())
        {
            if (child + 1 < _c.size() && _com(_c[child], _c[child + 1]))
            {
                child++;
            }
            if (_com(_c[parent], _c[child]))
            {
                std::swap(_c[parent], _c[child]);
                parent = child;
                child = 2 * parent + 1;
            }
            else
                break;
        }
    }

    // const T &val 参数防止传递对象时重新调用构造函数。
    void push(const T &val)
    {
        _c.push_back(val);
        shiftUp(_c.size() - 1);
    }

    void pop()
    {
        std::swap(_c[0], _c[_c.size() - 1]);
        _c.pop_back();
        shiftDown(0);
    }

    const T& top()
    {
        return _c.front();
    }
    size_t size()
    {
        return _c.size();
    }
    bool empty()
    {
        return _c.empty();
    }
};