优先队列
一. 定义
优先队列不再遵循先入先出的原则，而是分为两种情况：
- 最大优先队列，无论入队顺序，当前最大的元素优先出队。
- 最小优先队列，无论入队顺序，当前最小的元素优先出队。
因此可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。优先队列的入队和出队的时间复杂度和二叉堆结点上浮下沉的一样，都是O(logn)，n为队列元素个数
priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,queue等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式。
每一个点都带一个数字，这个数字越小，优先级越高。例如有{A,1} {C,5} {D,3}的元素，由于C的优先级比D低，故D做一个插队操作，排在队列前面：
1
2
| priority_queue<int, vector<int>,less<int>> q;
priority_queue<int,vector<int>,greater<int>> q;
|
二. 类型
1、基本类型
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
int main() {
priority_queue<int> a;
priority_queue<int,vector<int>,greater<int> > c;
priority_queue<string> b;
for(int i=0;i<5;i++)
{
a.push(i);
c.push(i);
}
while(!a.empty())
{
cout << a.top() << ' ';
a.pop();
}
cout <<endl;
while(!c.empty())
{
cout <<c.top() << ' ';
c.pop();
}
cout <<endl;
b.push("abc");
b.push("abcd");
b.push("cbd");
while(!b.empty())
{
cout <<b.top()<<' ';
b.pop();
}
cout <<endl;
return 0;
}
|
2、pair<type,type> 类型
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
int main() {
priority_queue<pair<int,int> > a;
pair<int,int> b(1,2);
pair<int,int> c(1,3);
pair<int,int> d(2,5);
a.push(b);
a.push(c);
a.push(d);
while(!a.empty()){
cout <<a.top().first <<' '<<a.top().second<< endl;
a.pop();
}
return 0;
}
输出结果：
2 5
1 3
1 2
|
3、自定义类型
HDU1873（看病要排队）
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
struct hospital
{
int level;
int id;
friend bool operator < (hospital c1,hospital c2)
{
if(c1.level!=c2.level)
return c1.level<c2.level;
else
return c2.id<c1.id;
}
};
int main()
{
int t;
hospital tmp;
string s;
int doc,level;
while(cin >>t)
{
priority_queue<hospital> p[4];
int cnt=0;
while(t--)
{
cin >> s;
if(s=="IN")
{
cnt++;
cin >> doc >> level;
tmp.level = level;
tmp.id = cnt;
p[doc].push(tmp);
}
else if(s=="OUT")
{
cin >>doc;
if(p[doc].empty())
cout << "EMPTY" <<endl;
else
{
tmp = p[doc].top();
p[doc].pop();
cout << tmp.id <<endl;
}
}
}
}
return 0;
}
|
前k个高频元素
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
| class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int>hash;
for(int n : nums) {
hash[n]++;
}
struct myComparison {
bool operator()(pair<int, int>&a, pair<int, int>&b) {
return a.second > b.second;
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, myComparison> que;
for(pair<int, int>a : hash) {
que.push(a);
if(que.size() > k) {
que.pop();
}
}
vector<int>ans;
while(!que.empty()) {
ans.emplace_back(que.top().first);
que.pop();
}
return ans;
}
};
|
三. 应用
3.1 BFS通过优先队列求最短路
放入队列的点是待处理的点，而出队的点是得到最短路的点
1）每次插入元素的时候，都要把元素和该元素到根节点的距离插入优先队列。
2）由此看出，C的优先级比B高，故会做插队操作：
STL的priority_queue能实现这个插队操作，直接使用即可
parent数组是记录每个结点的父节点。
3）随后C点出列，表示C已经访问过，则把C的邻接的且没有走过的点塞进优先队列。（可选择B、D、E）
4）同理，（B,3）的优先级最高，故把其放到队首并出列。B的父结点是C。
5）同理，优先级高的（D,4）放到队首出队，与D连接的有B、C、E、F，没有访问过的就只有E、F，故E F入队。
6）由于E点比之前的优先级高，故E放队首，并出队。
7）队列只剩下F没有走，故最后出列。
3.2 执行 K 次操作后的最大分数
传送门
通常在题目中求最大、最小值可以考虑使用堆这种数据结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
long long maxKelements(vector<int>& nums, int k) {
priority_queue<int, vector<int>, less<int>>que;
long long ans = 0;
for(int n : nums) {
que.push(n);
}
while(!que.empty() && k--) {
int n = que.top();
ans += n;
que.pop();
que.push((n + 2) / 3);
}
return ans;
}
};
|
