Namespaces
Variants

    std:: priority_queue

    From zh.cppreference.net
    C++
    Containers library
    std::priority_queue
    定义于头文件 <queue>
    template <

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

    > class priority_queue ;

    优先队列 是一种 容器适配器 ，它能够以常数时间复杂度访问最大（默认情况下）元素，但插入和提取操作的时间复杂度为对数级。

    用户可以提供一个自定义的 Compare 函数来改变排序规则，例如使用 std:: greater < T > 会使最小元素成为 top() 。

    使用 priority_queue 类似于在随机访问容器中管理 堆 ，其优势在于不会意外破坏堆结构。

    std::priority_queue 的所有成员函数均为 constexpr ：可以在常量表达式求值过程中创建和使用 std::priority_queue 对象。

    但 std::priority_queue 对象本身通常不能是 constexpr ，因为任何动态分配的存储都必须在同一常量表达式求值过程中释放。

    		(since C++26)

    目录

    模板参数

    T - 存储元素的类型。若 T 与 Container::value_type 不是同一类型，则程序非良构。
    Container - 用于存储元素的底层容器类型。该容器必须满足 SequenceContainer 要求，其迭代器必须满足 LegacyRandomAccessIterator 要求。此外，必须提供以下具有 常规语义 的函数：

    标准容器 std::vector （不包括 std::vector<bool> ）和 std::deque 满足这些要求。

    Compare - 提供严格弱序的 Compare 类型。

    注意 Compare 形参的定义方式为：若其第一个参数在弱序中 先于 第二个参数则返回 true 。但由于优先队列优先输出最大元素，故“先于”的元素实际上最后输出。即队列头部包含根据 Compare 所施加弱序的“最后”元素。

    成员类型

    成员 定义
    container_type Container
    value_compare Compare
    value_type Container::value_type
    size_type Container::size_type
    reference Container::reference
    const_reference Container::const_reference

    成员对象

    成员 描述
    容器 c
    		 底层容器
    (受保护成员对象)
    比较 comp
    		 比较函数对象
    (受保护成员对象)

    成员函数

    		构造 priority_queue
    (公开成员函数)
    		析构 priority_queue
    (公开成员函数)
    		为容器适配器赋值
    (公开成员函数)
    元素访问
    		访问顶部元素
    (公开成员函数)
    容量
    		检查容器适配器是否为空
    (公开成员函数)
    		返回元素数量
    (公开成员函数)
    修改器
    		插入元素并对底层容器排序
    (公开成员函数)
    (C++23)
    		插入元素范围并对底层容器排序
    (公开成员函数)
    (C++11)
    		原位构造元素并对底层容器排序
    (公开成员函数)
    		移除顶部元素
    (公开成员函数)
    (C++11)
    		交换内容
    (公开成员函数)

    非成员函数

    (C++11)
    		特化 std::swap 算法
    (函数模板)

    辅助类

    (C++11)
    		特化 std::uses_allocator 类型特征
    (类模板特化)
    (C++23)
    		std::priority_queue 的格式化支持
    (类模板特化)

    推导指引

    		(C++17 起)

    注释

    功能测试 宏 值 标准 功能特性
    __cpp_lib_containers_ranges 202202L (C++23) 支持范围 的容器构造与插入操作
    __cpp_lib_constexpr_queue 202502L (C++26) constexpr std::priority_queue

    示例

    运行此代码 
    #include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>
template<typename T>
void pop_println(std::string_view rem, T& pq)
{
    std::cout << rem << ": ";
    for (; !pq.empty(); pq.pop())
        std::cout << pq.top() << ' ';
    std::cout << '\n';
}
template<typename T>
void println(std::string_view rem, const T& v)
{
    std::cout << rem << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    println("data", data);
    std::priority_queue<int> max_priority_queue;
    // 填充优先队列
    for (int n : data)
        max_priority_queue.push(n);
    pop_println("max_priority_queue", max_priority_queue);
    // std::greater<int> 使最大优先队列表现为最小优先队列
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue1(data.begin(), data.end());
    pop_println("min_priority_queue1", min_priority_queue1);
    // 定义最小优先队列的第二种方式
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());
    pop_println("min_priority_queue2", min_priority_queue2);
    // 使用自定义函数对象比较元素
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;
    std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);
    pop_println("custom_priority_queue", custom_priority_queue);
    // 使用 lambda 表达式比较元素
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);
    for (int n : data)
        lambda_priority_queue.push(n);
    pop_println("lambda_priority_queue", lambda_priority_queue);
}

    输出： 

    data: 1 8 5 6 3 4 0 9 7 2
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1

    缺陷报告

    以下行为变更缺陷报告被追溯应用于先前发布的C++标准。

    缺陷报告 应用于 发布时的行为 正确行为
    LWG 307 C++98 Container 不能是 std::vector<bool> 允许
    LWG 2566 C++98 缺少对 Container::value_type 的要求 若 T 与 Container::value_type 类型不同则格式错误
    LWG 2684 C++98 priority_queue 接受比较器
    但缺少对应的成员类型定义     		已添加

    参见

    		可调整大小的连续数组
    (类模板)
    		空间优化的动态位集
    (类模板特化)
    		双端队列
    (类模板)