目录
一最后一块石头的重量
二数据流中的第K大元素
三前K个高频单词
四数据流的中位数
一最后一块石头的重量
oj链接：最后一块石头的重量
创建一个大根堆进行模拟即可！
class Solution
{
public:int lastStoneWeight(vector<int> &stones){priority_queue<int> q;for (auto &stone : stones){q.push(stone);}while (q.size() != 1){int a = q.top();q.pop();int b = q.top();q.pop();q.push(abs(a - b));}return q.top();}
};二数据流中的第K大元素
oj链接：数据流中的第 K 大元素
class KthLargest {
public:KthLargest(int k, vector<int>& nums) {_k=k;for(auto& num:nums){_q.push(num);if(_q.size()>_k) _q.pop();}}int add(int val) {_q.push(val);if(_q.size()>_k) _q.pop();return _q.top();}
private:priority_queue<int,vector<int>,greater<int>> _q;int _k;
};三前K个高频单词
oj链接：前K个高频单词
typedef pair<string, int> pr;class Solution
{
public:vector<string> topKFrequent(vector<string> &words, int k){// hash表统计个数unordered_map<string, int> hash;for (auto &word : words)hash[word]++;// 创建大小为k的堆,重写比较函数auto cmp = [](pr &p1, pr &p2) -> bool{return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);};priority_queue<pr, vector<pr>, decltype(cmp)> qe;// hash表的数据填到qe中for (auto &[a, b] : hash){qe.push({a, b});if (qe.size() > k)qe.pop();}vector<string> ret(k);// 倒着存，因为qe储存的数据是逆序的for (int i = k - 1; i >= 0; i--){ret[i] = qe.top().first;qe.pop();}return ret;}
};四数据流的中位数
oj链接：数据流的中位数
class MedianFinder {
public:MedianFinder() {}void addNum(int num) {ret.push_back(num);}double findMedian() {sort(ret.begin(),ret.end());if(ret.size()%2!=0){return ret[ret.size()/2];}else{return (ret[ret.size()/2]+ret[ret.size()/2-1])/2;}}vector<double> ret;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/
class MedianFinder {
public:MedianFinder() {}void addNum(int num) {_v.push_back((double)num);for(int i=0;i<_v.size()-1;i++){int end=i,tmp=_v[end+1];while(end>=0){if(_v[end]>tmp){_v[end+1]=_v[end];end--;}else{break;}}_v[end+1]=tmp;}}double findMedian() {if(_v.size()%2!=0) return _v[_v.size()/2];else return (_v[_v.size()/2-1]+_v[_v.size()/2])/2;}vector<double> _v;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/
class MedianFinder
{
public:MedianFinder(){}void addNum(int num){int m = _left.size(), n = _right.size();if (m == n){if (_left.size() == 0 || _left.top() >= num)_left.push(num);else{_right.push(num);_left.push(_right.top());_right.pop();}}else // m==n+1{if (_left.top() >= num){_left.push(num);_right.push(_left.top());_left.pop();}else_right.push(num);}}double findMedian(){if (_left.size() == _right.size() + 1)return _left.top();elsereturn (_left.top() + _right.top()) / 2;}private:priority_queue<double> _left; // 大堆priority_queue<double, vector<double>, greater<double>> _right; // 小堆
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/以上便是优先级队列相关的算法题，有问题欢迎在评论区指正！