Loading... ## priority_queue 包含头文件 `<queue>` 定义：priority_queue<T> var; 访问：与队列不同，优先队列只能通过 top() 访问队首元素 常见 API： 1. q.push(x); 入队 2. q.pop(); 队首元素出队 3. q.top(); 获取队首元素 4. q.empty(); 检查是否为空 5. q.size(); 队列中元素个数 ## 优先级设置 ```cpp priority_queue<Type, Container, Functional>; //Type 是数据类型，Container 为保存数据的容器，Functional 为元素比较方式 priority_queue<int, vector<int>, less<int>> q1; priority_queue<int> q2; // 两者等价 // 默认大顶堆，使用 vector 容器，从大到小队列 priority_queue<int, vector<int>, greater<int>> q3; // 小顶堆，从小到大排列 ``` ## 算子 `不需要使用 () 调用` 当数据类型为自定义类或结构体时，需要重载相应操作符。定义排序规则方式： ### 重载 operater< 或 operator> 此处有一个非常难搞的问题 - 一个是重载哪种符号 - 一个是比较时用大于还是小于号 - 引用的时候是用 less 还是 greater 有一个配套 ```cpp // 小顶堆 bool operator<(const Edge& rhs) const // 类内定义，只需要一个参数 { return cost>rhs.cost; } priority_queue<Edge,vector<Edge>,less<Edge>> priQue; priority_queue<Edge> priQue; //等价 // 大顶堆 bool operator<(const Edge& rhs) const // 类内定义，只需要一个参数 { return cost<rhs.cost; } priority_queue<Edge,vector<Edge>,less<Edge>> priQue; priority_queue<Edge> priQue; //等价 ``` 为方便只使用前面两种，都可以直接缺省使用 - 无论什么堆都重载 < - 大堆 <，小堆 > - 不缺省都用 less ### 重写仿函数 cmp，声明比较类 cmp return 中符号，与类内重载 < 相同 - < 是大顶堆 - > 是小顶堆 ```cpp // 力扣 1584 struct Edge { public: int start; int end; int cost; Edge(int s, int e, int c): start(s), end(e), cost(c) {} // overloaded 'operator<' must be a binary operator (has 3 parameters) //bool operator>(const Edge& rhs) const // 类内定义，只需要一个参数 //{ // return cost>rhs.cost; //} }; struct cmp { bool operator()(Edge a, Edge b) { return a.cost > b.cost; // 是大于 } }; //priority_queue<Edge,vector<Edge>,greater<Edge>> priQue; priority_queue<Edge,vector<Edge>,cmp> priQue; priQue.emplace(0,0,0); priQue.emplace(2,2,2); priQue.emplace(1,1,1); while(priQue.size()) { cout<<priQue.top().cost; cout<<" "; priQue.pop(); } ``` # sort 函数 默认升序排列，即从小到大。 ## 自定义排序方式 ### lambda 函数 ```cpp struct Edge { public: int start; int end; int cost; Edge(int s, int e, int c): start(s), end(e), cost(c) {} }; sort(vec.begin(), vec.end(), [&](const Edge& lsh, const Edge& rhs){ return lsh.cost < rhs.cost; // 升序 从小到大 // return lsh.cost<rhs.cost; 从大到小 }); ``` ### 自定义比较函数 - 自定义比较函数要能够在 sort 引用的范围内，因此可以`声明为静态函数` - sort `引用时不需要 ()` ```cpp struct Edge { public: int start; int end; int cost; Edge(int s, int e, int c): start(s), end(e), cost(c) {} }; class Solution { public: static bool cmp(Edge& lhs, Edge& rhs) { return lhs.cost < rhs.cost; // 升序 } void test(vector<int>& nums, int target) { vector<Edge> vec; vec.emplace_back(0, 0, 0); vec.emplace_back(2, 2, 2); vec.emplace_back(1, 1, 1); sort(vec.begin(), vec.end(), cmp); } }; ``` ### 重载 < 运算符 ```cpp struct Edge { public: int start; int end; int cost; Edge(int s, int e, int c): start(s), end(e), cost(c) {} bool operator<(const Edge& rhs) { return cost < rhs.cost; // 升序 } }; sort(vec.begin(), vec.end()); ``` ### 声明比较类 需要使用 (） ```cpp struct cmp { bool operator()(Edge& lhs, Edge& rhs) { return lhs.cost < rhs.cost; // 升序 } }; sort(vec.begin(), vec.end(), cmp()); ``` # 总结 1. 优先队列有 3 种方法，sort 有 4 种 2. 默认排序方式 1. 优先队列反直觉，< 是大，> 是小 2. sort 正好相反 3. 只有 sort 函数在调用比较类时需要使用 () 最后修改：2021 年 07 月 29 日 03 : 55 PM © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付