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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Node{
int a,b;
Node(){}
Node(int aa,int bb):a(aa),b(bb){}
// 二级排序，a相同时按照b升序排序，否则按照a升序排序
// (a,b): (1,1)<(1,2)<(2,1)<(2,2)
// 这里重载的大于号和小于号在逻辑上等价
bool operator < (const Node &r) const{
if(a==r.a)
return b<r.b;
else
return a<r.a;
}
bool operator > (const Node &r) const{
if(a==r.a)
return b>r.b;
else
return a>r.a;
}
};
int main(){
//priority_queue 是基于堆实现的优先队列
// .size()返回当前优先队列的元素个数
// empty()为true表示当前队列为空，false表示不空
priority_queue<int> tmp_q;
cout<<tmp_q.size()<<endl; //0
cout<<tmp_q.empty()<<endl; //1
tmp_q.push(1);
cout<<tmp_q.size()<<endl; //1
cout<<tmp_q.empty()<<endl; //0
tmp_q.pop();
cout<<tmp_q.size()<<endl; //0
cout<<tmp_q.empty()<<endl; //1
// priority_queue<int> 表示队列中存储的元素是int类型（STL模板类）
// 默认priority_queue表示队列按照less出队
// 后出队的元素比先出队的元素要小，出队的元素越来越小，所以是less
// push 加入元素
// top 返回队首元素
// pop 队首元素出队
priority_queue<int> q;
q.push(5);
q.push(6);
cout<<q.top()<<endl; //6
q.pop();
cout<<q.top()<<endl; //5
q.pop();
// greater 表示后出队的元素比先出队的元素要大, 出队的元素越来越大，所以是greater
priority_queue<int, vector<int>, greater<int>> q_greater;
// <>中第二个参数vector<int>表示优先队列中使用vector<int> 存储元素，可以更换成deque
// 第二个参数中更换的其他类型应支持.begin(),.end(),.push(),.pop()等操作
// 绝大多数情况都使用vector<>，极少需要更换
// 例子：priority_queue<int, deque<int>, greater<int>> q_greater;
q_greater.push(5);
q_greater.push(6);
cout<<q_greater.top()<<endl; //5
q_greater.pop();
cout<<q_greater.top()<<endl; //6
q_greater.pop();
// 更换为double类型，出队法则是less
priority_queue<double, vector<double>, less<double>> q_less;
q_less.push(5.2);
q_less.push(6.6);
cout<<q_less.top()<<endl; //6.6
q_less.pop();
cout<<q_less.top()<<endl; //5.2
q_less.pop();
// 自定义类Node的priority_queue 使用greater需要对元素重载大于号
priority_queue<Node, vector<Node>, greater<Node>> q_greater_node;
q_greater_node.push(Node(1,1));
q_greater_node.push(Node(1,2));
q_greater_node.push(Node(2,1));
q_greater_node.push(Node(2,2));
cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl; // 1 1
q_greater_node.pop();
cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl; // 1 2
q_greater_node.pop();
cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl; // 2 1
q_greater_node.pop();
cout<<q_greater_node.top().a<<" "<<q_greater_node.top().b<<endl; // 2 2
q_greater_node.pop();
// 自定义类Node的priority_queue 使用less需要对元素重载小于号
priority_queue<Node, vector<Node>, less<Node>> q_less_node;
q_less_node.push(Node(1,1));
q_less_node.push(Node(1,2));
q_less_node.push(Node(2,1));
q_less_node.push(Node(2,2));
cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl; // 2 2
q_less_node.pop();
cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl; // 2 1
q_less_node.pop();
cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl; // 1 2
q_less_node.pop();
cout<<q_less_node.top().a<<" "<<q_less_node.top().b<<endl; // 1 1
q_less_node.pop();
return 0;
}
|