1.priority_queue概述priority_queue是C标准模板库(STL)中的容器适配器提供优先级队列功能。它保证优先级最高的元素总是位于队列前端默认情况下是最大堆实现最大元素优先。2. 基本特性优先级排序元素按优先级排序默认最大元素在前容器适配器基于其他序列容器实现默认vector限制访问只允许访问顶部元素高效操作插入和删除操作时间复杂度为O(log⁡2n)O(\log_2 n)O(log2​n)堆结构底层使用堆数据结构实现3. 头文件与声明123456#include queue // 注意priority_queue也在queue头文件中usingnamespacestd;priority_queueint pq1;// 默认最大堆基于vectorpriority_queueint, vectorint, greaterint pq2;// 最小堆priority_queuestring pq3;4. 构造函数与初始化4.1 默认构造1priority_queueint pq;// 创建空的最大堆4.2 基于比较函数构造1234567// 自定义比较函数structCompare {booloperator()(inta,intb) {returna b;// 最小堆}};priority_queueint, vectorint, Compare custom_pq;4.3 使用已有数据初始化12vectorint vec {3, 1, 4, 1, 5};priority_queueint pq(vec.begin(), vec.end());// 使用迭代器范围构造5. 容量操作5.1empty()123if(pq.empty()) {cout 优先级队列为空;}5.2size()1cout 优先级队列大小: pq.size();6. 元素访问6.1top()123if(!pq.empty()) {cout 最高优先级元素: pq.top();}7. 修改操作7.1push()123pq.push(10);// 插入元素pq.push(20);pq.push(5);7.2emplace()1pq.emplace(15);// 原地构造元素(避免拷贝)7.3pop()123if(!pq.empty()) {pq.pop();// 移除最高优先级元素}7.4swap()(C11)12priority_queueint pq2;pq.swap(pq2);// 交换两个优先级队列8. 完整示例1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include iostream#include queue#include vector#include functional // 用于greaterintusingnamespacestd;intmain() {// 最大堆示例priority_queueint max_heap;max_heap.push(30);max_heap.push(10);max_heap.push(50);max_heap.emplace(20);cout 最大堆元素: ;while(!max_heap.empty()) {cout max_heap.top() ;max_heap.pop();}cout endl;// 最小堆示例priority_queueint, vectorint, greaterint min_heap;min_heap.push(30);min_heap.push(10);min_heap.push(50);min_heap.emplace(20);cout 最小堆元素: ;while(!min_heap.empty()) {cout min_heap.top() ;min_heap.pop();}cout endl;// 自定义比较函数示例structPoint {intx, y;Point(intx,inty) : x(x), y(y) {}booloperator(constPoint other)const{return(x*x y*y) (other.x*other.x other.y*other.y);}};priority_queuePoint point_pq;point_pq.emplace(1, 2);point_pq.emplace(3, 4);point_pq.emplace(0, 1);cout 按与原点的距离排序的点: ;while(!point_pq.empty()) {Point p point_pq.top();cout ( p.x , p.y ) ;point_pq.pop();}cout endl;return0;}9. 底层容器与比较函数9.1 底层容器选择priority_queue可以基于以下容器实现vector默认随机访问性能好适合堆操作deque两端操作高效但内存使用不如vector紧凑9.2 比较函数lessT默认最大堆大元素优先greaterT最小堆小元素优先自定义比较函数实现复杂排序逻辑1234567// 自定义比较函数示例按字符串长度排序structLengthCompare {booloperator()(conststring a,conststring b) {returna.length() b.length();// 长度大的优先}};priority_queuestring, vectorstring, LengthCompare length_pq;10. 实际应用示例10.1 合并KKK个有序链表12345678910111213141516171819202122232425262728293031323334structListNode {intval;ListNode *next;ListNode(intx) : val(x), next(nullptr) {}};structCompareNode {booloperator()(ListNode* a, ListNode* b) {returna-val b-val;// 最小堆}};ListNode* mergeKLists(vectorListNode* lists) {priority_queueListNode*, vectorListNode*, CompareNode pq;for(auto node : lists) {if(node) pq.push(node);}ListNode dummy(0);ListNode* tail dummy;while(!pq.empty()) {tail-next pq.top();pq.pop();tail tail-next;if(tail-next) {pq.push(tail-next);}}returndummy.next;}10.2 查找前KKK个高频元素123456789101112131415161718192021vectorint topKFrequent(vectorint nums,intk) {unordered_mapint,int freq;for(intnum : nums) freq[num];priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq;for(auto [num, count] : freq) {pq.push({count, num});if(pq.size() k) {pq.pop();}}vectorint result;while(!pq.empty()) {result.push_back(pq.top().second);pq.pop();}returnresult;}11. 性能考虑时间复杂度push(): O(log⁡2n)O(\log_2 n)O(log2​n)pop(): O(log⁡2n)O(\log_2 n)O(log2​n)top(): O(1)O(1)O(1)empty(): O(1)O(1)O(1)size(): O(1)O(1)O(1)空间复杂度O(n)O(n)O(n)底层容器选择影响vector内存局部性好通常性能更优deque在某些情况下可能提供更好的性能12. 注意事项调用top()或pop()前必须检查队列是否为空priority_queue不提供迭代器无法遍历内部元素自定义比较函数需要严格弱序