算法笔记（十一）——优先级队列(堆)

文章目录

最后一块石头的重量
数据流中的第 K 大元素
前K个高频单词
数据流的中位数

优先级队列是一种特殊的队列，元素按照优先级从高到低（或从低到高）排列，高优先级的元素先出队，可以用堆来实现

堆是一种二叉树的结构，有两种主要类型：最大堆和最小堆
下面附上之前写的两篇博客：
优先级队列(priority_queue）
数据结构堆（Heap）的实现

最后一块石头的重量

题目：最后一块石头的重量

在这里插入图片描述
思路

创建一个大根堆priority_queue<int> pq;默认情况下是大根堆，将所以石头加入到堆中
用一个循环处理，直至堆中元素剩余元素个数小于等于1
依次取出堆顶元素x,y其中x >= y
若 x = y ，则pop掉两元素；
若x > y，则pop掉两元素，之后将x - y，push进堆
循环结束后，若剩一个元素，即为其重量；若堆为空，则返回0

C++代码

class Solution 
{
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> pq; for(auto e : stones) pq.push(e);while(pq.size() > 1) {int x = pq.top();pq.pop();int y = pq.top();pq.pop();if (x > y)pq.push(x - y);   }return pq.size() == 0 ? 0 : pq.top();  }
};

数据流中的第 K 大元素

题目：数据流中的第 K 大元素

在这里插入图片描述
思路

经典topK问题
创建一个大小为k的堆
循环：依次进堆，判断堆的大小是否超过k

找的是第k大元素，维护一个大小为k的最小堆，保证堆中只有前 k大的元素

将新元素加入最小堆中，然后检查堆的大小是否超过k，如果超过则弹出堆顶元素
最终返回当前堆顶元素，即为第 k大的元素
在 add 操作后始终保持堆中的元素为前 K 大的元素
而堆顶元素即为第k大的元素。

C++代码

class KthLargest 
{// 创建一个大小为 k 的小根堆priority_queue<int, vector<int>, greater<int>> heap;int _k;
public:KthLargest(int k, vector<int>& nums) {_k = k;for(int& x : nums){heap.push(x);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);*/

前K个高频单词

题目：前K个高频单词

在这里插入图片描述
思路

经典topK问题
创建一个大小为k的堆
循环：依次进堆，判断堆的大小是否超过k

找出前k个出现次数最多的，所以整体我们建小堆
对比较函数按照要求实现，不能用库里的；
如果两个字符串出现频率相同，那么我们让两字符串中字典序较小的排在前面，否则我们让出现频率较高的排在前面
C++代码

class Solution 
{typedef pair<string, int> PSI;struct cmp{bool operator()(const PSI& x, const PSI& y){if(x.second == y.second) return x.first < y.first;else return x.second > y.second;}};
public:vector<string> topKFrequent(vector<string>& words, int k) {// 统计单词的频次unordered_map<string, int> hash;for(auto e:words) hash[e]++;// 创建一个大小为 k 的堆priority_queue<PSI, vector<PSI>, cmp> heap;for(auto&e:hash){heap.push(e);if(heap.size() > k) heap.pop();}// 答案vector<string> ret(k);for(int i = k - 1; i >= 0; i--){ret[i] = heap.top().first;heap.pop();}return ret;}
};

数据流的中位数

题目：数据流的中位数

在这里插入图片描述
思路

利用大小堆来维护数据流的中位数

初始化两个优先队列
left 用于存放较小的一半元素（大根堆）
right 用于存放较大的一半元素（小根堆）
个数为偶数时，大根堆元素个数m等于小根堆元素个数n，即m = n；
个数为奇数时，大根堆left多放一个，即m = n + 1
x，y 分别为大根堆、小根堆堆顶元素

当add()添加元素时，我们按照下述方法维护两个堆

当m == n时，

num <= x || m == 0，num直接进入left堆

num > x ，num先进入right堆，再将right堆定元素放入left堆

当m == n + 1时，

num <= x，num直接进入left堆，再将left堆定元素放入堆right

num > x ，num直接进入right堆

C++代码

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);left.push(right.top());right.pop();}}else{if(num <= left.top()){left.push(num);right.push(left.top());left.pop();}else right.push(num);}}double findMedian() {if(left.size() == right.size()) return (left.top() + right.top()) / 2.0;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();*/