介绍
队列具有先进先出的特性，添加元素只能在队尾插入，删除只能删除队首元素。
优先级队列出队只能是队列中优先级最高的元素，而不是队首的元素。
出队后优先级队列需要重新维护。
因此，优先级队列和堆很类似。
优先级队列的定义
1
2
| template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >
class priority_queue;
|
1
2
3
4
5
6
|
priority_queue<int> pq1;
priority_queue<int, vector<int>, less<int>> pq2;
priority_queue<int, vector<int>, greater<int>> pq3;
|
基本操作
top()
返回元素中第一个元素的引用
push()
插入一个元素，重新维护堆
pop()
删除优先级最高的元素，重新维护堆
size()
返回容器中有效元素的大小
empty()
判空
代码示例：
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
| int main()
{
priority_queue<int> pq1;
pq1.push(1);
pq1.push(2);
pq1.push(3);
pq1.push(4);
pq1.push(5);
cout << pq1.top() << endl;
pq1.pop();
cout << pq1.top() << endl;
cout << pq1.size() << endl;
return 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
| class Data
{
public:
Data(int i, int d)
:id(d)
, data(d)
{}
int GetData() const
{
return data;
}
private:
int id;
int data;
};
class cmp
{
public:
bool operator() (Data& d1, Data& d2)
{
return d1.GetData() < d2.GetData();
}
};
int main()
{
Data* d1 = new Data(0, 1);
Data* d2 = new Data(0, 2);
Data* d3 = new Data(0, 3);
priority_queue<Data,vector<Data>,cmp> pq;
pq.push(*d1);
pq.push(*d2);
pq.push(*d3);
while(!pq.empty())
{
cout << (pq.top().GetData()) << endl;
pq.pop();
}
return 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
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
| #pragma once
#include<iostream>
using namespace std;
#include<vector>
namespace pq
{
template<class T, class Container = vector<T>, class Compare = std::less<T>>
class priority_queue
{
public:
priority_queue()
{}
template <class Inputinterpreator>
priority_queue(Inputinterpreator first, Inputinterpreator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
void adjust_up(size_t child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
}
else
{
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void adjust_down(size_t parent)
{
Compare com;
size_t child = (parent * 2) + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
child = child + 1;
}
if (com(_con[parent], _con[child]))
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
parent = child;
child = (parent * 2) + 1;
}
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}
|
其实就是堆排序的思路
1
2
3
4
5
6
7
8
9
10
11
12
| int main(){
pq::priority_queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout<<q.top()<<endl;
q.pop();
cout<<q.top()<<endl;
q.pop();
cout<<q.top()<<endl;
q.pop();
}
|
例题
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq;
for(auto n:nums){
pq.push(n);
}
while(k>1){
pq.pop();
k--;
}
return pq.top();
}
};
|
