priority_queue 是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与释出。

可用用户提供的 Compare 更改顺序，例如，用 std::greater 将导致最小元素作为 top() 出现。

用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

默认情况下priority_queue内部是以”降序“排列的，即默认大顶堆。

一、使用

定义于头文件

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

模板形参

• T - 存储的元素类型。若 T 与 Container::value_type 不是同一类型则行为未定义。 (C++17 起)
• Container - 用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求，而其迭代器必须满足遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求。另外，它必须提供拥有通常语义的下列函数：front()``push_back()``pop_back()标准容器 std::vector 和 std::deque 满足这些要求。
• Compare - 提供严格弱序的比较 (Compare) 类型。

堆实现

大顶堆：priority_queue默认实现大顶堆，也可将priority_queue模板第三个参数显示设置 std::less。

小顶堆：priority_queue模板第三个参数显示设置 std::greater，实现小顶堆。

二、priority_queue自定义排序

前面说到 priority_queue 容器适配器时，还遗留一个问题，即当 头文件提供的排序方式（std::less 和 std::greater）不再适用时，如何自定义一个满足需求的排序规则。

首先来看看 std::less 和 std::greater 各自的底层实现。实际上， 头文件中的 std::less 和 std::greater ，各自底层实现采用的都是函数对象的方式。

比如，std::less 的底层实现代码为：

template <typename T>
struct less {
    //定义新的排序规则
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs < _rhs;
    }
};

std::greater 的底层实现代码为：

template <typename T>
struct greater {
    bool operator()(const T &_lhs, const T &_rhs) const {
        return _lhs > _rhs;
    }
};

可以看到，std::less 和 std::greater 底层实现的唯一不同在于，前者使用 < 号实现从大到小排序，后者使用 > 号实现从小到大排序。

仿照 std::less 和 std::greater 的底层实现代码，我们可以自己定义比较函数，然后作为参数传入priority_queue使用。

参考文章：

cppreference::priority_queue

STL priority_queue自定义排序实现方法详解