恒美微站 Logo 恒美微站
  • 首页
  • 关于我们
  • 建站服务
  • 主题模板
  • 案例展示
  • 资讯中心
  • 联系我们

C++中priority_queue的实现

  • 首页
  • 资讯中心
  • /
  • C++中priority_queue的实现

相关资讯

Git 忽略文件大小写 2026/8/14 20:41:05
Agent 的搜索引擎:Agentic Resource Discovery 规范,以及它解决不了的信任问题 2026/8/14 20:41:05
认知引力统一场论:通过信息-物理对偶性构建物理第一性原理与认知现象的数理联系 2026/8/14 20:41:05

最新资讯

从手工流水线到智能驾驶舱:AI Native时代CI/CD的范式演进与实践
RisohEditor(文件资源编译器)
运维控制台升级:从只读监控到实时诊断的架构设计与安全实践
十分钟精通《三步点睛》策略:全套指标解析
本地大模型RAG实战:node-llama-cpp与内存检索集成指南
百度输入法美化包安装指南:iOS与安卓双平台全解析

今日推荐

青岛煜鹏网站建设公司如何帮助传统企业实现数字化转型破局与增长路径
内蒙古生产建设兵团四师三十四团知青网站:承载岁月记忆与青春荣耀的精神家园
梅州市住房与城乡建设局官网:获取权威建筑信息、政策解读与民生服务的最佳平台入口

本周热门

5分钟告别提取码焦虑:baidupankey如何智能破解百度网盘资源锁
如何快速生成中国车牌图片:Python开源工具完整指南
当 LLM 遇见大文档:主流开源项目如何处理上下文超限

本月精选

如何用DamaiHelper实现演唱会门票的智能自动化抢购:完整技术解决方案指南
第4篇:59 倍性能差距的索引瓶颈定位——一次教科书级的全表扫描调优
终极歌词批量下载神器:5分钟解决离线音乐库歌词同步难题

C++中priority_queue的实现

发布时间:2026/8/14 20:46:05
C++中priority_queue的实现 一、priority_queue 核心定义std::priority_queue优先队列是 C STL 中的适配器容器基于其他容器实现本质是一个「堆结构」——队列中的元素会按照优先级自动排序而非按插入顺序。核心特性每次访问/弹出的都是优先级最高的元素默认是最大值可自定义为最小值底层实现默认基于std::vector也可指定std::deque不支持std::list因为堆需要随机访问头文件必须包含queue。二、基本用法默认大顶堆1. 初始化与核心操作1234567891011121314151617181920212223242526#include iostream#include queue // 必须包含usingnamespacestd;intmain() {// 1. 初始化默认是大顶堆最大值优先priority_queueint pq;// 2. 插入元素pushO(log n) 复杂度pq.push(3);pq.push(1);pq.push(5);pq.push(2);// 3. 访问队首top返回优先级最高的元素最大值cout 队首元素最大值 pq.top() endl;// 输出5// 4. 弹出队首pop删除优先级最高的元素O(log n) 复杂度pq.pop();cout 弹出后队首 pq.top() endl;// 输出3// 5. 判空empty、大小sizecout 是否为空 (pq.empty() ?是:否) endl;// 输出否cout 元素个数 pq.size() endl;// 输出3// 6. 遍历无迭代器需弹出所有元素while(!pq.empty()) {cout pq.top() ;// 输出3 2 1pq.pop();}return0;}2. 关键说明top()仅返回队首元素不删除pop()仅删除队首元素无返回值需先top()再pop()无clear()成员函数清空优先队列需手动弹出所有元素或赋值空队列pq priority_queueint();不支持随机访问无法直接访问中间元素只能通过top()访问队首。三、自定义优先级小顶堆/自定义规则默认的priority_queue是「大顶堆」最大值优先可通过以下方式修改优先级1. 实现小顶堆最小值优先方式1指定比较函数greaterT1234567891011121314151617181920#include iostream#include queue#include vector // 显式指定底层容器usingnamespacestd;intmain() {// 模板参数元素类型, 底层容器类型, 比较函数priority_queueint, vectorint, greaterint pq;pq.push(3);pq.push(1);pq.push(5);pq.push(2);cout 小顶堆队首最小值 pq.top() endl;// 输出1pq.pop();cout 弹出后队首 pq.top() endl;// 输出2return0;}方式2对元素取反适用于简单类型1234567// 插入时取反弹出时再取反模拟小顶堆priority_queueint pq;pq.push(-3);pq.push(-1);pq.push(-5);pq.push(-2);cout 模拟小顶堆队首 -pq.top() endl;// 输出12. 自定义结构体/类的优先级需重载比较运算符operator或自定义比较函数。示例结构体按指定字段排序12345678910111213141516171819202122232425262728293031#include iostream#include queue#include stringusingnamespacestd;// 定义结构体存储学生姓名和分数structStudent {string name;intscore;// 重载 运算符注意优先队列用 比较且规则与直觉相反// 需求分数高的优先级高大顶堆booloperator(constStudent other)const{// 若 this-score other.score则 other 优先级更高returnscore other.score;}};intmain() {priority_queueStudent pq;pq.push({Alice, 85});pq.push({Bob, 92});pq.push({Charlie, 78});// 输出优先级最高的元素分数最高的Bobcout 最高分 pq.top().name pq.top().score endl;// Bob 92pq.pop();cout 次高分 pq.top().name pq.top().score endl;// Alice 85return0;}自定义比较函数适用于复杂规则12345678910111213141516171819202122232425262728#include iostream#include queue#include string#include functional // 需包含for functionusingnamespacestd;structStudent {string name;intscore;};// 自定义比较函数分数低的优先级高小顶堆structCompareStudent {booloperator()(constStudent a,constStudent b) {returna.score b.score;// 与小顶堆的 greater 逻辑一致}};intmain() {priority_queueStudent, vectorStudent, CompareStudent pq;pq.push({Alice, 85});pq.push({Bob, 92});pq.push({Charlie, 78});cout 最低分 pq.top().name pq.top().score endl;// Charlie 78return0;}四、底层原理堆结构priority_queue的核心是二叉堆完全二叉树所有操作均基于堆的特性插入push将元素添加到堆尾然后「上浮sift up」调整堆确保父节点优先级高于子节点O(log n)弹出pop将堆顶元素与堆尾元素交换删除堆尾然后「下沉sift down」调整堆O(log n)访问队首top直接返回堆顶元素O(1)。五、常见应用场景Top K 问题如找数组中前 K 大/前 K 小的元素用小顶堆存前 K 大大顶堆存前 K 小12345678// 示例找数组中前3大的元素vectorint nums {5, 2, 9, 1, 7, 6, 8};priority_queueint, vectorint, greaterint pq;// 小顶堆for(intnum : nums) {pq.push(num);if(pq.size() 3) pq.pop();// 保持堆大小为3}// 此时堆中是前3大的元素7,8,9但顺序是从小到大贪心算法如任务调度、哈夫曼编码、最短路径Dijkstra 算法实时排序需频繁获取最大值/最小值的场景如事件优先级处理。六、注意事项底层容器限制只能用支持随机访问的容器vector/deque不能用list无随机访问比较函数规则默认lessT大顶堆a b则 b 优先级高greaterT小顶堆a b则 b 优先级高性能插入/弹出为 O(log n)访问队首为 O(1)遍历需弹出所有元素O(n log n)线程安全无内置线程安全多线程需手动加锁。总结核心特性说明排序规则默认大顶堆可自定义为小顶堆/自定义规则核心操作push插入、top查队首、pop删队首时间复杂度push/pop: O(log n)top: O(1)底层容器默认 vector可指定 deque适用场景Top K、贪心算法、实时优先级处理priority_queue 是 C 中处理「优先级排序」的核心容器重点掌握自定义优先级的两种方式greaterT/自定义比较函数以及 Top K 问题的经典用法。

关于恒美微站

恒美微站专注于为个体商户、工作室提供极简自助建站服务,让每个人都能轻松拥有专业网站。

快速链接

  • 关于我们
  • 建站服务
  • 主题模板
  • 案例展示
  • 资讯中心

服务项目

  • 可视化建站
  • 拖拽编辑
  • 主题定制
  • SEO 优化
  • 网站托管

联系方式

  • 📍 地址:北京市朝阳区建国路 88 号
  • 📞 电话:400-888-8888
  • ✉️ 邮箱:info@hmyw.cn
  • 🕐 时间:周一至周日 9:00-18:00

© 2024 恒美微站 hmyw.cn 版权所有 | 京 ICP 备 12345678 号