本文为c++容器系列第十篇.
主要测试了priority_queue相关的方法，主要作为代码备份方便之后遗忘时查询。
优先队列是对容器的一个封装，形成的adapter，默认是最大堆，通过top()可以获得最大值。改变compare函数就可以把它变成最小堆。
每次插入或者pop出一个元素之后，只需要调整堆，不需要将全部元素重新排序。堆调整的比较次数是O(log n)，top()是O(1)；如果底层vector扩容，还会有元素搬移的开销。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main(){
// 声明
priority_queue<int> pq; // 默认是最大堆，可以通过下面的方式声明为最小堆。
priority_queue<int,vector<int>,greater<int>> pq1;
// 也可以通过如下方式直接将一个容器内的所有元素装进priority_queue中。
vector<int> a = {1,4,2,3};
priority_queue<int> pq2(less<int>(),a); // 最大堆
cout<<"qp2.top():"<<pq2.top()<<endl;
// 比较器类型也要写进模板参数，不能只改构造函数的参数。
// priority_queue<int,vector<int>,greater<int>> pq3(greater<int>(),a); //最小堆
// cout<<pq3.top()<<endl;
//下面针对pq进行操作演示
pq.push(2);
pq.push(1);
pq.emplace(3);
pq.emplace(4);
cout<<"pq.size()"<<pq.size()<<endl;
cout<<"pq.empty()"<<pq.empty()<<endl;
pq.pop();
cout<<"after pop,pq.size()"<<pq.size()<<endl;
// 遍历: priority_queue默认是最大堆，每次的通过top()获得的元素就是最大值。
cout<<"pq = ";
while(!pq.empty()){
cout<<pq.top()<<'\t';
pq.pop();
}
cout<<endl;
return 0;
}
/* 运行结果。
qp2.top():4
pq.size()4
pq.empty()0
after pop,pq.size()3
pq = 3 2 1
Program ended with exit code: 0
*/
|