C++中priority_queue的实现

一、priority_queue 核心定义

std::priority_queue（优先队列）是 C++ STL 中的适配器容器（基于其他容器实现），本质是一个「堆结构」——队列中的元素会按照优先级自动排序，而非按插入顺序。

• 核心特性：每次访问/弹出的都是优先级最高的元素（默认是最大值，可自定义为最小值）；
• 底层实现：默认基于std::vector，也可指定std::deque（不支持std::list，因为堆需要随机访问）；
• 头文件：必须包含<queue>。

二、基本用法（默认大顶堆）

1. 初始化与核心操作

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <iostream> #include <queue> // 必须包含 usingnamespacestd; intmain() { // 1. 初始化：默认是大顶堆（最大值优先） priority_queue<int> pq; // 2. 插入元素（push）：O(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）、大小（size） cout <<"是否为空："<< (pq.empty() ?"是":"否") << endl;// 输出：否 cout <<"元素个数："<< pq.size() << endl;// 输出：3 // 6. 遍历（无迭代器，需弹出所有元素） while(!pq.empty()) { cout << pq.top() <<" ";// 输出：3 2 1 pq.pop(); } return0; }

2. 关键说明

• top()：仅返回队首元素，不删除；pop()：仅删除队首元素，无返回值（需先top()再pop()）；
• 无clear()成员函数：清空优先队列需手动弹出所有元素，或赋值空队列（pq = priority_queue<int>();）；
• 不支持随机访问：无法直接访问中间元素，只能通过top()访问队首。

三、自定义优先级（小顶堆/自定义规则）

默认的priority_queue是「大顶堆」（最大值优先），可通过以下方式修改优先级：

1. 实现小顶堆（最小值优先）

方式1：指定比较函数greater<T>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <iostream> #include <queue> #include <vector> // 显式指定底层容器 usingnamespacestd; intmain() { // 模板参数：<元素类型, 底层容器类型, 比较函数> priority_queue<int, vector<int>, greater<int>> pq; pq.push(3); pq.push(1); pq.push(5); pq.push(2); cout <<"小顶堆队首（最小值）："<< pq.top() << endl;// 输出：1 pq.pop(); cout <<"弹出后队首："<< pq.top() << endl;// 输出：2 return0; }

方式2：对元素取反（适用于简单类型）

1 2 3 4 5 6 7

// 插入时取反，弹出时再取反，模拟小顶堆 priority_queue<int> pq; pq.push(-3); pq.push(-1); pq.push(-5); pq.push(-2); cout <<"模拟小顶堆队首："<< -pq.top() << endl;// 输出：1

2. 自定义结构体/类的优先级

需重载比较运算符（operator<），或自定义比较函数。

示例：结构体按指定字段排序

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <iostream> #include <queue> #include <string> usingnamespacestd; // 定义结构体：存储学生姓名和分数 structStudent { string name; intscore; // 重载 < 运算符（注意：优先队列用 < 比较，且规则与直觉相反） // 需求：分数高的优先级高（大顶堆） booloperator<(constStudent& other)const{ // 若 this->score < other.score，则 other 优先级更高 returnscore < other.score; } }; intmain() { priority_queue<Student> pq; pq.push({"Alice", 85}); pq.push({"Bob", 92}); pq.push({"Charlie", 78}); // 输出优先级最高的元素（分数最高的Bob） cout <<"最高分："<< pq.top().name <<" "<< pq.top().score << endl;// Bob 92 pq.pop(); cout <<"次高分："<< pq.top().name <<" "<< pq.top().score << endl;// Alice 85 return0; }

自定义比较函数（适用于复杂规则）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <iostream> #include <queue> #include <string> #include <functional> // 需包含（for function） usingnamespacestd; structStudent { string name; intscore; }; // 自定义比较函数：分数低的优先级高（小顶堆） structCompareStudent { booloperator()(constStudent& a,constStudent& b) { returna.score > b.score;// 与小顶堆的 greater 逻辑一致 } }; intmain() { priority_queue<Student, vector<Student>, CompareStudent> pq; pq.push({"Alice", 85}); pq.push({"Bob", 92}); pq.push({"Charlie", 78}); cout <<"最低分："<< pq.top().name <<" "<< pq.top().score << endl;// Charlie 78 return0; }

四、底层原理：堆结构

priority_queue的核心是二叉堆（完全二叉树），所有操作均基于堆的特性：

1. 插入（push）：将元素添加到堆尾，然后「上浮（sift up）」调整堆，确保父节点优先级高于子节点（O(log n)）；
2. 弹出（pop）：将堆顶元素与堆尾元素交换，删除堆尾，然后「下沉（sift down）」调整堆（O(log n)）；
3. 访问队首（top）：直接返回堆顶元素（O(1)）。

五、常见应用场景

1. Top K 问题：如找数组中前 K 大/前 K 小的元素（用小顶堆存前 K 大，大顶堆存前 K 小）；

   1 2 3 4 5 6 7 8

   // 示例：找数组中前3大的元素 vector<int> nums = {5, 2, 9, 1, 7, 6, 8}; priority_queue<int, vector<int>, greater<int>> pq;// 小顶堆 for(intnum : nums) { pq.push(num); if(pq.size() > 3) pq.pop();// 保持堆大小为3 } // 此时堆中是前3大的元素（7,8,9），但顺序是从小到大

2. 贪心算法：如任务调度、哈夫曼编码、最短路径（Dijkstra 算法）；
3. 实时排序：需频繁获取最大值/最小值的场景（如事件优先级处理）。

六、注意事项

1. 底层容器限制：只能用支持随机访问的容器（vector/deque），不能用list（无随机访问）；
2. 比较函数规则：
   • 默认less<T>：大顶堆（a < b则 b 优先级高）；
   • greater<T>：小顶堆（a > b则 b 优先级高）；
3. 性能：插入/弹出为 O(log n)，访问队首为 O(1)，遍历需弹出所有元素（O(n log n)）；
4. 线程安全：无内置线程安全，多线程需手动加锁。

总结

核心特性	说明
排序规则	默认大顶堆，可自定义为小顶堆/自定义规则
核心操作	push（插入）、top（查队首）、pop（删队首）
时间复杂度	push/pop: O(log n)，top: O(1)
底层容器	默认 vector，可指定 deque
适用场景	Top K、贪心算法、实时优先级处理

priority_queue 是 C++ 中处理「优先级排序」的核心容器，重点掌握自定义优先级的两种方式（greater<T>/自定义比较函数），以及 Top K 问题的经典用法。