【算法】堆与优先级队列
【ps】本篇有 4 道 leetcode OJ。
目录
一、算法简介
二、相关例题
1）最后一块石头的重量
.1- 题目解析
.2- 代码编写
2）数据流中的第 K 大元素
.1- 题目解析
.2- 代码编写
3）前K个高频单词
.1- 题目解析
.2- 代码编写
4）数据流的中位数
.1- 题目解析
.2- 代码编写
一、算法简介
普通队列的特点是先进先出，元素在队尾入队，而从队首出队。优先级队列则不同，队列中的每个元素都被赋予了一个权值，权值较高的元素排在最前优先出队。它一般默认通过一个大根堆（即权值以从高到低排列）实现，表现为一个以 vector 为底层的完全二叉树。
优先级队列常与模拟算法一起出题。除了要掌握如何对优先级队列建大根堆或小根堆，还要能够不借助 STL 提供的优先级队列来自己实现堆这种数据结构，因为这是面试场上常考的（欲知堆的更多细节，请见【数据结构】树之二叉树）。
二、相关例题
1）最后一块石头的重量
1046. 最后一块石头的重量
.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 大元素
703. 数据流中的第 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个高频单词
692. 前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）数据流的中位数
295. 数据流的中位数
.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();
*/