std::priority_queue是基于堆实现的自动排序容器，默认为最大堆，仅允许访问顶部元素，支持自定义比较器以实现最小堆或结构体排序，常用于Dijkstra算法、任务调度等需动态获取最优先级元素的场景。

std::priority_queue 是 c++ 标准库中定义在 <queue> 头文件里的容器适配器，用于实现一个自动排序的队列结构。它基于堆（heap）数据结构，默认情况下是一个最大堆，也就是说每次取出的元素都是当前队列中最大的。

优先队列的基本结构特点

std::priority_queue 并不是一个独立的容器，而是基于其他序列容器（如 vector 或 deque）构建的堆结构。其核心特性包括：

• 自动排序：插入元素后，内部会自动调整堆结构，确保优先级最高的元素位于顶部。
• 只能访问顶部元素：只允许访问或移除堆顶元素（即最高优先级），不能遍历或直接访问其他元素。
• 默认是最大堆：使用 std::less 作为比较器，顶部为最大值。
• 底层容器可配置：通常使用 vector 作为默认底层容器，也可以指定 deque 等支持随机访问的容器。

基本用法与常用操作

创建和使用 priority_queue 非常直观。以下是最常见的操作方式：

 #include <queue> #include <iostream>  std::priority_queue<int> pq; // 默认最大堆  pq.push(10); pq.push(30); pq.push(20);  std::cout << pq.top() << "n"; // 输出 30 pq.pop(); std::cout << pq.top() << "n"; // 输出 20 

主要成员函数有：

立即学习“C++免费学习笔记（深入）”；

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

0

查看详情

• push(element)：插入元素，并重新调整堆结构。
• pop()：移除堆顶元素（不返回值）。
• top()：返回堆顶元素的引用（最大或最小，取决于比较器）。
• empty()：判断队列是否为空。
• size()：返回元素个数。

自定义比较方式（最小堆或结构体排序）

如果需要最小堆，可以通过指定比较器来实现：

 std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq; min_pq.push(30); min_pq.push(10); min_pq.push(20); std::cout << min_pq.top() << "n"; // 输出 10 

对于自定义类型，比如结构体，可以重载比较函数或提供仿函数：

 struct Person {     int age;     std::string name; };  // 自定义比较器：按年龄升序（小顶堆） auto cmp = [](const Person& a, const Person& b) {     return a.age > b.age; // 注意：这里 > 表示优先级更高的是更小的数 }; std::priority_queue<Person, std::vector<Person>, decltype(cmp)> pq_person(cmp); 

常见应用场景

std::priority_queue 常用于需要动态维护“最优先”元素的场景：

• 实现 Dijkstra 最短路径算法中的节点选取。
• 合并多个有序链表时，快速获取最小头节点。
• 任务调度系统中，按优先级执行任务。
• 求数据流中第 K 大/小的元素。

基本上就这些。std::priority_queue 使用简单，性能高效，只要理解它是“只能取最大或最小”的自动排序容器，就能避免误用。注意比较器逻辑，尤其是自定义类型时别写反了优先级方向。基本上就这些。