C++ 优先队列 自定义优先规则。
基础用法省略。
需要包含的头文件
#include <queue>
#include <functional>
不同的优先规则:针对基础数据类型。
默认大根堆
声明方法
priority_queue<int, vector<int>, greater<int> > q; // 小根堆 priority_queue<int, vector<int>, less<int> > q; // 大根堆
应用举例
#include<bits/stdc++.h> using namespace std; priority_queue<int,vector<int>,greater<int> > p; int main() { int n=10; while(n--) { int temp; cin>>temp; p.push(temp); } while (!p.empty()) { cout<<p.top()<<' '; p.pop(); } }
重载运算符实现自定义权重小根堆
方式一:
struct qnode { int v; int c; qnode(int v=0,int c=0):v(v),c(c){} bool operator <(const qnode &r)const { return c>r.c; } }; priority_queue<qnode>que;
完整应用代码:dijkstra模板题
方式二:
struct Node{ int x, y; Node(int a = 0, int b= 0):x(a), y(b) {} }; struct cmp{ bool operator() (const Node& a, const Node& b ){ if (a.x == b.x) return a.y > b.y; return a.x > b.x; } }; priority_queue<Node, vector<Node>, cmp> q;
方式三:
struct Node{ int x, y; Node(int a = 0, int b= 0):x(a), y(b) {} }; bool operator < (const Node& a, const Node& b ){ if (a.x == b.x) return a.y > b.y; return a.x > b.x; } priority_queue<Node> q;