一、priority_queue
C++中实现大/小顶堆的数据结构是priority_queue，其默认是大顶堆，如果要实现小顶堆，需要传入第三个参数greater<int>。
priority_queue结构有三个传参：
- 第一个参数type：进行排序的数据类型
- 第二个参数container：底层存储根堆的容器类型，默认是
vector，且只能是数组类型，所以不能是list等
- 第三个参数compare：比较函数，用于实现大顶堆或小顶堆
函数原型：
1
2
3
4
| #include <queue>
priority_queue<int, vector<int>, greater<int>> q;
|
二、比较函数的设计
priority_queue如果要自定义比较逻辑，也是通过传入第三个参数(比较函数)来实现的。
sort的比较函数中
- 如果要实现升序，比较函数
return a < b
- 如果要实现降序，比较函数
return a > b
而priority_queue中
- 如果要实现大根堆（类似升序），比较函数
return a[0] < b[0]
- 如果要实现小根堆（类似降序），比较函数
return a[0] > b[0]
2.1 大根堆less与小根堆greater
通过两个比较函数less和greater实现大/小根堆，分别用于实现大根堆和小根堆。
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
|
int main(){
vector<vector<int>> vec = { {11, 13}, {12, 14}, {11, 12}, {15, 16} };
priority_queue<vector<int>, vector<vector<int>>, less<vector<int>>> big_heap;
for (auto x : vec) {
big_heap.push(x);
}
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> small_heap;
for (auto x : vec) {
small_heap.push(x);
}
cout << "大根堆：" << endl;
while (!big_heap.empty()) {
auto x = big_heap.top();
big_heap.pop();
cout << x[0] << " - " << x[1] << endl;
}
cout << "-----------------" << endl;
cout << "小根堆：" << endl;
while (!small_heap.empty()) {
auto x = small_heap.top();
small_heap.pop();
cout << x[0] << " - " << x[1] << endl;
}
return 0;
}
|
2.2 自定义比较函数
如果要实现自定义比较函数，可以通过重写仿函数来实现。
- 大根堆：
return a[0] < b[0]
- 小根堆：
return a[0] > b[0]
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
|
struct cmpBig {
bool operator()(const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0]) {
return a[1] < b[1];
}
else {
return a[0] < b[0];
}
}
};
struct cmpSmall {
bool operator()(const vector<int>& a, const vector<int>& b) {
if (a[0] == b[0]) {
return a[1] > b[1];
}
else {
return a[0] > b[0];
}
}
};
int main() {
vector<vector<int>> vec = { {11, 13}, {12, 14}, {11, 12}, {15, 16} };
priority_queue<vector<int>, vector<vector<int>>, cmpBig> big_heap;
for (auto x : vec) {
big_heap.push(x);
}
priority_queue<vector<int>, vector<vector<int>>, cmpSmall> small_heap;
for (auto x : vec) {
small_heap.push(x);
}
cout << "大根堆：" << endl;
while (!big_heap.empty()) {
auto x = big_heap.top();
big_heap.pop();
cout << x[0] << " - " << x[1] << endl;
}
cout << "-----------------" << endl;
cout << "小根堆：" << endl;
while (!small_heap.empty()) {
auto x = small_heap.top();
small_heap.pop();
cout << x[0] << " - " << x[1] << endl;
}
return 0;
}
|
三、真题
leetcode 347 前 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
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
| class Solution {
public:
struct cmp{
bool operator()(const pair<int, int> &a, const pair<int, int> &b){
return a.second > b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m_map;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> small_heap;
for(int i:nums){
m_map[i]++;
}
for(auto it = m_map.begin(); it != m_map.end(); ++it){
small_heap.push(*it);
if(small_heap.size() > k){
small_heap.pop();
}
}
vector<int> res;
while(!small_heap.empty()){
auto kv = small_heap.top();
res.push_back(kv.first);
small_heap.pop();
}
return res;
}
};
|
