#include <queue>

std::priority_queue<int> pq; // 创建一个存储 int 类型的优先级队列

pq.push(5);  // 添加 5 到队列
pq.push(3);  // 添加 3 到队列
pq.push(8);  // 添加 8 到队列

int topElement = pq.top();  // 获取最高优先级的元素（不移除）
pq.pop();  // 移除最高优先级的元素

bool isEmpty = pq.empty();  // 检查队列是否为空

int size = pq.size();  // 返回队列中元素的个数

template <
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;  //具体比较逻辑就需要在各自类里实现
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

// 定义优先级队列模板类，有三个模板参数
// T表示存储在优先级队列中的元素类型
// Container表示用于存储元素的底层容器类型，默认是vector<T>
// Compare表示用于确定元素优先级顺序的比较对象类型，默认是less<T>，用于按小于关系确定优先级（通常意味着值越大优先级越高）
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
private:
    // 向下调整函数，用于维护堆的性质（大根堆为例），从给定的父节点开始向下调整元素位置
    void AdjustDown(int parent)
    {
        // 创建比较对象，用于比较元素的优先级
        Compare com;

        // 计算父节点parent的左孩子节点索引，在完全二叉树中，左孩子索引为 2 * parent + 1，因为下标此时从0开始
        size_t child = parent * 2 + 1;
        // 只要孩子节点索引小于底层容器中元素个数，说明存在孩子节点，继续循环调整
        while (child < _con.size())
        {
            // 如果右孩子节点存在（索引不越界），并且通过比较对象判断右孩子的优先级大于左孩子的优先级
            if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
            {
                // 将孩子索引指向右孩子，因为右孩子优先级更高，后续要和父节点比较并可能交换
                ++child;
            }

            // 如果通过比较对象判断父节点的优先级小于当前孩子节点的优先级（不符合大根堆性质）
            if (com(_con[parent], _con[child]))
            {
                // 交换父节点和当前孩子节点的值，以维护大根堆性质
                swap(_con[child], _con[parent]);
                // 更新父节点索引为当前孩子节点的索引，继续向下检查交换后的子树是否满足堆性质
                parent = child;
                // 重新计算新的孩子节点索引，继续向下调整过程
                child = parent * 2 + 1;
            }
            else
            {
                // 如果当前父节点和孩子节点满足堆性质，不需要再调整，直接退出循环
                break;
            }
        }
    }

    // 向上调整函数，用于在插入新元素后维护堆的性质，从给定的孩子节点开始向上调整元素位置
    void AdjustUp(int child)
    {
        // 创建比较对象，用于比较元素的优先级
        Compare com;

        // 计算孩子节点child的父节点索引，在完全二叉树中，父节点索引为 (child - 1) / 2
        int parent = (child - 1) / 2;
        // 只要孩子节点索引大于0，说明不是根节点，继续向上循环调整
        while (child > 0)
        {
            // 如果通过比较对象判断父节点的优先级小于当前孩子节点的优先级（不符合堆性质）
            if (com(_con[parent], _con[child]))
            {
                // 交换父节点和当前孩子节点的值，以维护堆性质
                swap(_con[child], _con[parent]);
                // 更新孩子节点索引为当前父节点的索引，继续向上检查交换后的子树是否满足堆性质
                child = parent;
                // 重新计算新的父节点索引，继续向上调整过程
                parent = (child - 1) / 2;
            }
            else
            {
                // 如果当前父节点和孩子节点满足堆性质，不需要再调整，直接退出循环
                break;
            }
        }
    }

public:
    // 默认构造函数，不做任何特殊初始化操作，底层容器会使用其默认构造进行初始化
    priority_queue()
    {}

    // 范围构造函数，接受两个迭代器，表示一个范围，用于初始化优先级队列
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
    {
        // 遍历给定的迭代器范围，将每个元素插入到底层容器_con中
        while (first!= last)
        {
            _con.push_back(*first);
            ++first;
        }

        // 构建堆，从倒数第一个非叶节点开始，对每个非叶节点调用AdjustDown函数进行向下调整，以构建大根堆
        for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
        {
            AdjustDown(i);
        }
    }

    // 弹出函数，用于移除优先级队列中的最高优先级元素（队首元素）
    void pop()
    {
        // 将队首元素（根节点）和最后一个元素交换位置，方便移除最高优先级元素
        swap(_con[0], _con[_con.size() - 1]);
        // 移除最后一个元素，即原来的队首元素（最高优先级元素）
        _con.pop_back();

        // 对新的根节点调用AdjustDown函数进行向下调整，以维护堆的性质
        AdjustDown(0);
    }

    // 插入函数，用于向优先级队列中插入一个新元素
    void push(const T& x)
    {
        // 将新元素插入到底层容器的末尾
        _con.push_back(x);

        // 对新插入的元素（在容器末尾，即最后一个位置）调用AdjustUp函数进行向上调整，以维护堆的性质
        AdjustUp(_con.size() - 1);
    }

    // 获取最高优先级元素（队首元素）的函数，返回元素的常引用，不允许通过此引用修改元素
    const T& top()
    {
        return _con[0];
    }

    // 判断优先级队列是否为空的函数，如果底层容器为空则返回true，表示队列为空，否则返回false
    bool empty()
    {
        return _con.empty();
    }

    // 获取优先级队列中元素个数的函数，返回底层容器中元素的数量
    size_t size()
    {
        return _con.size();
    }

private:
    // 用于存储元素的底层容器，类型由模板参数Container指定，默认是vector<T>
    Container _con;
};