当前位置: 首页 > news >正文

优先队列

在 C++ 中,priority_queue(优先队列)是一种容器适配器,它提供了一种按照优先级自动排序的队列功能。与普通队列(queue)的“先进先出(FIFO)”不同,priority_queue 中每次出队的元素都是当前队列中优先级最高的元素。

核心特性

  1. 默认排序:默认情况下,priority_queue 采用大顶堆(max-heap) 结构,即每次出队的是最大的元素(数值越大优先级越高)。
  2. 底层容器:默认基于 vector 实现(也可指定为 deque),通过堆算法维护元素的优先级顺序。
  3. 不可直接访问中间元素:只能访问队顶(优先级最高)的元素,不支持迭代器遍历。

头文件与定义

使用 priority_queue 需要包含头文件 <queue>,定义格式如下:

#include <queue>
using namespace std;// 默认:大顶堆(元素类型为 T,底层容器为 vector,比较器为 less<T>)
priority_queue<T> pq;// 自定义:指定底层容器和比较器(例如小顶堆)
priority_queue<T, Container, Compare> pq;

常用操作

操作 功能说明 时间复杂度
pq.push(val) 插入元素 val 到队列,并维护优先级 O(log n)
pq.pop() 移除队顶(优先级最高)的元素 O(log n)
pq.top() 返回队顶元素的引用(不删除) O(1)
pq.empty() 判断队列是否为空(空返回 true O(1)
pq.size() 返回队列中元素的个数 O(1)

示例:默认大顶堆

#include <iostream>
#include <queue>
using namespace std;int main() {priority_queue<int> pq;// 插入元素pq.push(30);pq.push(10);pq.push(50);pq.push(20);// 输出队顶并移除,直到为空while (!pq.empty()) {cout << pq.top() << " ";  // 每次输出当前最大元素pq.pop();}// 输出:50 30 20 10return 0;
}

自定义优先级(小顶堆)

如果需要小顶堆(每次出队最小元素),可以通过指定比较器 greater<T> 实现:

#include <iostream>
#include <queue>
#include <vector>  // 需显式指定底层容器
using namespace std;int main() {// 小顶堆:元素类型 int,底层容器 vector,比较器 greater<int>priority_queue<int, vector<int>, greater<int>> pq;pq.push(30);pq.push(10);pq.push(50);pq.push(20);while (!pq.empty()) {cout << pq.top() << " ";  // 每次输出当前最小元素pq.pop();}// 输出:10 20 30 50return 0;
}

自定义类型的优先级

对于自定义结构体/类,需要通过重载运算符自定义比较器指定优先级:

方法1:重载 < 运算符(用于默认大顶堆)

#include <iostream>
#include <queue>
using namespace std;struct Person {string name;int age;// 重载 <:年龄大的优先级高(用于大顶堆)bool operator<(const Person& other) const {return age < other.age;  // 注意:堆内部用 < 比较,返回 true 表示当前对象优先级低}
};int main() {priority_queue<Person> pq;pq.push({"Alice", 25});pq.push({"Bob", 30});pq.push({"Charlie", 20});while (!pq.empty()) {cout << pq.top().name << "(" << pq.top().age << "), ";pq.pop();}// 输出:Bob(30), Alice(25), Charlie(20),return 0;
}

方法2:自定义比较器(灵活控制优先级)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;struct Person {string name;int age;
};// 自定义比较器:年龄小的优先级高(用于小顶堆)
struct CompareAge {bool operator()(const Person& a, const Person& b) {return a.age > b.age;  // 注意:返回 true 表示 a 优先级低于 b}
};int main() {priority_queue<Person, vector<Person>, CompareAge> pq;pq.push({"Alice", 25});pq.push({"Bob", 30});pq.push({"Charlie", 20});while (!pq.empty()) {cout << pq.top().name << "(" << pq.top().age << "), ";pq.pop();}// 输出:Charlie(20), Alice(25), Bob(30),return 0;
}

总结

  • priority_queue 适用于需要动态获取最大/最小元素的场景(如任务调度、贪心算法等)。
  • 默认是大顶堆,通过 greater<T> 可改为小顶堆。
  • 自定义类型需通过重载运算符或比较器指定优先级规则。
  • 不支持随机访问,仅能操作队顶元素,插入和删除的时间复杂度为 O(log n)。

在 C++ 中,priority_queue(优先队列)和 queue(普通队列)都是容器适配器,但它们的核心行为和应用场景有显著区别,主要体现在元素的访问和移除顺序上。

1. 核心特性对比

特性 queue(普通队列) priority_queue(优先队列)
元素顺序规则 遵循“先进先出(FIFO)”原则:先插入的元素先被移除。 遵循“优先级最高先出”原则:每次移除的是当前队列中优先级最高的元素(与插入顺序无关)。
底层数据结构 默认基于 deque 实现(也可指定 list)。 默认基于 vector 实现(也可指定 deque),内部通过堆算法维护优先级。
访问权限 只能访问队头(front)和队尾(back)元素。 只能访问优先级最高的元素(队顶,top),无法直接访问其他元素(包括队尾)。
典型应用场景 需按插入顺序处理元素的场景(如广度优先搜索 BFS、缓存队列、任务排队等)。 需动态获取“最大/最小元素”的场景(如贪心算法、任务调度、TOP-K 问题等)。

2. 操作上的差异

两者的基本操作(pushpopemptysize)名称相同,但行为逻辑不同:

  • push 操作

    • queue:将元素插入队尾,不改变其他元素顺序。
    • priority_queue:将元素插入后,会通过堆调整重新排序,确保队顶始终是优先级最高的元素。
  • pop 操作

    • queue:移除队头(最先插入的元素)。
    • priority_queue:移除队顶(当前优先级最高的元素),并重新调整堆结构维持优先级。
  • 元素访问

    • queuefront() 获取队头元素,back() 获取队尾元素。
    • priority_queue 只能用 top() 获取优先级最高的元素(无 frontback)。

3. 示例对比

普通队列(queue)示例

#include <iostream>
#include <queue>
using namespace std;int main() {queue<int> q;q.push(3);  // 队尾:3q.push(1);  // 队尾:1(队列:3, 1)q.push(2);  // 队尾:2(队列:3, 1, 2)while (!q.empty()) {cout << q.front() << " ";  // 依次输出队头(先入先出)q.pop();}// 输出:3 1 2return 0;
}

优先队列(priority_queue)示例

#include <iostream>
#include <queue>
using namespace std;int main() {priority_queue<int> pq;  // 默认大顶堆(最大值优先)pq.push(3);pq.push(1);pq.push(2);while (!pq.empty()) {cout << pq.top() << " ";  // 依次输出优先级最高的元素(最大的)pq.pop();}// 输出:3 2 1return 0;
}

4. 总结

  • queue 是“顺序依赖”的容器,适合按插入顺序处理元素,核心是FIFO
  • priority_queue 是“优先级依赖”的容器,适合需要动态获取最值的场景,核心是优先级排序
  • 两者均不支持随机访问,只能通过特定接口(front/top)访问特定元素,且插入/删除操作的时间复杂度不同(queue 为 O(1),priority_queue 为 O(log n))。
http://www.hskmm.com/?act=detail&tid=28259

相关文章:

  • 学习ReAct并使用langgraph实现一个简单的ReAct AI Agent!!
  • abc 408 d~f
  • RMQ与LCA学习笔记
  • mamba-硬件感知算法
  • Java1
  • 完整教程:lua代码解析1
  • 二维数点
  • gitee和github如何修改仓库名并且保持与原远程仓库的连接?(手把手教学) - 实践
  • 2025.10.10总结 - A
  • [20251010]建立完善tpt的prr.sql脚本.txt
  • 第十一篇
  • testtest
  • 题解:AT_arc138_f [ARC138F] KD Tree
  • SP33 TRIP - Trip 个人题解
  • 经营不是老板一个人的事 - 智慧园区
  • Codeforces Round 1051 (Div. 2)[A ~E]
  • 如何在 Spring Boot 应用中配置多个 Spring AI 的 LLM 客户端
  • 使用eBPF技术保护FastAPI安全
  • 项目案例作业2:对案例进行面向对象分析
  • JavaSE
  • CF2064E Mycraft Sand Sort
  • Servlet笔记
  • 第一个博客
  • k8s 主节点重启后 从节点 get 异常 - 教程
  • 多维索引技术优化数据湖查询性能
  • Umi-OCR_文字识别工具 免安装使用教程(附下载安装包)!永久免费,开源离线OCR识别软件下载
  • 【汇总】OPPO r9m 分区名、分区功能
  • 04_线程池实现
  • #D251010D. 未命名 10 (unnamed)
  • 【JAVA】从入门到放弃-01-HelloWorld - 指南