【ps】本篇有 4 道 leetcode OJ。
目录
一、算法简介
普通队列的特点是先进先出,元素在队尾入队,而从队首出队。优先级队列则不同,队列中的每个元素都被赋予了一个权值,权值较高的元素排在最前优先出队。它一般默认通过一个大根堆(即权值以从高到低排列)实现,表现为一个以 vector 为底层的完全二叉树。
优先级队列常与模拟算法一起出题。除了要掌握如何对优先级队列建大根堆或小根堆,还要能够不借助 STL 提供的优先级队列来自己实现堆这种数据结构,因为这是面试场上常考的(欲知堆的更多细节,请见【数据结构】树之二叉树)。
二、相关例题
1)最后一块石头的重量
.1- 题目解析
对于从一个序列中选出最大值,不难想到堆排序和优先级队列。我们可以将数组中的元素全部插入优先级队列中,然后依此从堆顶取两个元素进行“粉碎”,这两个元素其中一个一定是当前数组中最大的,另一个一定是次大的。如果它们两个相等,就不作处理,相当于两个都“粉碎”了;如果不相等,就将它们的差值入队......以此类推,直至优先级队列中没有元素或仅剩一个元素。
.2- 代码编写
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> heap;
for(auto x:stones)heap.push(x);
while(heap.size()>1)
{
int a=heap.top();
heap.pop();
int b=heap.top();
heap.pop();
if(a>b)heap.push(a-b);
}
return heap.size()?heap.top():0;
}
};
2)数据流中的第 K 大元素
.1- 题目解析
这是一道典型的 Top-K 问题,其解决方法有堆排序、基于快排的快速选择算法。尽管快速选择算法的时间复杂度为 O(n),堆排序为 O(n*logK),但面对海量数据时,快速选择算法的空间复杂度颇高,因此此处选用更优的堆排序来解题。
具体方式是,创建一个大小为 k 的堆,如果是找第 k 大(排降序)就创建小根堆,找第 k 小(排升序)就创建大根堆。然后将待排序的元素依此进堆,每次进堆都判断一下堆的大小是否超过 k,如此,堆顶存放的就一直是第 k 大或第 k 小的元素。
.2- 代码编写
class KthLargest {
priority_queue<int,vector<int>,greater<int>> heap;//排降序建小根堆
int _k;
public:
//显示的构造函数
KthLargest(int k, vector<int>& nums) {
_k=k;
for(auto x:nums)
{
//先将元素入堆进行排序
heap.push(x);
//堆的大小超过k,就把堆顶元素取出,只留下第k大的元素在堆顶
if(heap.size()>_k)
heap.pop();
}
}
int add(int val) {
heap.push(val);
if(heap.size()>_k)
heap.pop();
return heap.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
3)前K个高频单词
.1- 题目解析
这也是一道典型的 Top-K 问题。在进行堆排序找到前 k 个高频单词之前,我们需要先对数组中的单词出现的频次进行统计,这样才能进行堆排序。
而特别的,一般情况下应按单词出现频率由高到低排序,此时应建小堆;当不同的单词有相同频次时, 就要按字典序来排序,此时应建大堆。那么,我们就需要对建堆的排序函数进行特殊处理。
由于堆顶存放的是频次前 k 大中频次最小的单词,因此从堆顶依此取元素并插入到数组中的时候,需要将元素从后往前插入到数组中,或者从前往后插入,最终将数组逆序。
.2- 代码编写
class Solution {
typedef pair<string,int> PSI;
struct cmp
{
bool operator()(const PSI& a,const PSI& b)
{
if(a.second==b.second)
return a.first<b.first;
return a.second>b.second;
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k) {
//1.用哈希表统计频次
unordered_map<string,int> hash;
for(auto&s:words)hash[s]++;
//2.建堆
priority_queue<PSI,vector<PSI>,cmp> heap;
for(auto& x:hash)
{
heap.push(x);
if(heap.size()>k)heap.pop();
}
//3.统计结果
vector<string> ret(k);
for(int i=k-1;i>=0;i--)
{
ret[i]=heap.top().first;
heap.pop();
}
return ret;
}
};
4)数据流的中位数
.1- 题目解析
要找到一个中位数,这个数据序列必须是有序的。我们可以将一个排好序的序列一分为二,将序列左边的所有元素放入大根堆里,将序列右边的所有元素放入小根堆里,如此,大根堆的堆顶就是序列左边的最大元素,小根堆的堆顶就说序列右边的最小元素,此时只要把这两个堆顶元素相加除以 2,就能得到整个序列的中位数了。
设 num 是一个待插入堆的元素,m 为序列左边的元素个数,n 为序列右边的元素个数,则:
.2- 代码编写
class MedianFinder {
priority_queue<int> left;
priority_queue<int,vector<int>,greater<int>> right;
public:
MedianFinder() {
}
void addNum(int num) {
if(left.size()==right.size())
{
if(left.empty()||num<=left.top())
{
left.push(num);
}
else
{
right.push(num);
int rightTop=right.top();
right.pop();
left.push(rightTop);
}
}
else if(left.size()==right.size()+1)
{
if(num<=left.top())
{
left.push(num);
int leftTop=left.top();
left.pop();
right.push(leftTop);
}
else
{
right.push(num);
}
}
}
double findMedian() {
if(left.size()==right.size())
return (left.top()+right.top())/2.0;
else
return left.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
标签:优先级,队列,元素,int,算法,heap,size
From: https://blog.csdn.net/waluolandao/article/details/142243279