一、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 问题的经典用法。