优先队列(堆)的实现

优先队列(堆)

优先队列也就是堆

什么是堆呢?

堆是一颗完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆,小于等于左右孩子就是小顶堆。

priority_queue<int , vector<int>,greater<int>> heap;//创建小根堆
1
2
3
4
5
6
7
8
9
10
11

引用头文件 #include<queue>
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容


1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::priority_queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;

//自定义比较类型
//左大于右就会建立小顶堆,反而建立大顶堆

// 小顶堆--pair类型的比较
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};

练习题目

Leetcode-前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
class Solution {
public:
// 小顶堆
class mycmp{
public:
bool operator() (const pair<int,int> &l,const pair<int,int> &r)
{
return l.second>r.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
priority_queue<pair<int,int>,vector<pair<int,int>>,mycmp> heap;
for(int i=0;i<nums.size();++i)
{
++map[nums[i]];
}
for(auto i : map){
heap.push(i);
if(heap.size()>k)
{
heap.pop();
}
}
vector<int> ans;

while(!heap.empty())
{
ans.push_back(heap.top().first);
heap.pop();
}
return ans;
}
};