Merlin's Blog
Just record something
Toggle navigation
Merlin's Blog
Home
Scratch基础教程
About Me
Archives
Tags
priority_queue使用方法
优先队列
2020-05-18 11:05:23
266
0
0
merlin
优先队列
**priority_queue**优先队列，默认是大根堆，写法如下： ``` priority_queue<int, vector<int>, less<int> > q; //队列保存整型数据 //less<int>右边有一个空格，如果不加，则变成>>运算，会报错 ``` 但平时默认大根堆，可以省略$less<int>$，可以这样写 ``` priority_queue<int> q; ``` **小根堆写法** ``` priority_queue<int, vector<int>, greater<int> > q; ``` 这个没法省略，不然无法区分了。 ###**注意** **greater**使内置类型从大到小排序，而**less**从小到大。 但在**优先队列**中，刚好相反，即 **sort**用**greater**排序，则**a[0]**到**a[n-1]**有大到小排序。 **priority_queue**用**greater**排序，则先取出的是最小值。 ##**队列是结构体，如何使用优先队列？** 结构体属于自建类型，不是内置类型(int、long long等)，所以比较规则需要自己写，C++提供了**运算符重载**，具体看下面例子。 ``` #include<bits/stdc++.h> using namespace std; struct Item{ int s; bool operator < (const Item& rhs) const{ return s < rhs.s; } }; priority_queue<Item> q; Item a[20]; int main() { srand(unsigned(time(NULL))); for(int i = 0; i < 20; i++){ int x = rand() % 100; a[i].s = x; q.push(Item(x)); } cout<<"原始数据：\n"; for(int i = 0; i < 20; i++) cout<<a[i].s << " "; cout<<endl; sort(a,a+20); cout<<"排序后的数据：\n"; for(int i = 0; i < 20; i++) cout<<a[i].s << " "; cout<<endl; cout<<"优先队列顺序：\n"; for(int i = 0; i < 20; i++){ Item x = q.top(); cout<<x.s<<" "; q.pop(); } return 0; } ```  可以看到**sort**和**priority_queue**刚好相反，虽然同一个规则。 访问优先队列第一个元素： ``` int x = q.top(); ```
Pre:
精品高考全真模拟卷（技术）
Next:
2019-CSP-入门级解析
0
likes
266
Weibo
Wechat
Tencent Weibo
QQ Zone
RenRen
Table of content
merlin
