简介
优先级队列其实就是堆
默认大根堆
小根堆：greater<T>
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;priority_queue 没有迭代器， 不能for（auto e:pq);
不改变原来pq，查看所有pq元素，只能先拷贝；
优先级队列接口：
1.最后一块石头的重量
link:1046. 最后一块石头的重量 - 力扣（LeetCode）
思路：
priority_quue大根堆 + 模拟
code
class Solution {
public:int lastStoneWeight(vector<int>& stones) {// 优先级队列// 默认大根堆priority_queue<int, vector<int>> pq(stones.begin(), stones.end());while(pq.size() > 1){int stn1 = pq.top();pq.pop();int stn2 = pq.top();pq.pop();int sub = abs(stn1 - stn2);if(sub) pq.push(sub);}return pq.empty() ? 0 : pq.top();}
};2.数据流中的第k大元素
link:703. 数据流中的第 K 大元素 - 力扣（LeetCode）
思路：
topk问题
最小堆：，建立并维护最小堆即可，最小堆中存储前K大的数，heap.top()就是第k大的数。
code
class KthLargest {
public:priority_queue<int, vector<int>, greater<int>> sm;int _k;KthLargest(int k, vector<int>& nums):_k(k){for(int i = 0; i < nums.size(); i++){sm.push(nums[i]);}while(sm.size() > _k) sm.pop();}int add(int val) {sm.push(val);if(sm.size() > _k)sm.pop();return sm.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个高频单词
link:692. 前K个高频单词 - 力扣（LeetCode）
思路：
小根堆
注意不可用引用接收top，不然pop时top会自动变化，这是个大坑，很难发现问题
code
class Solution {
public:struct mygreater{bool operator()(pair<string, int> p1, pair<string, int> p2){if(p1.second == p2.second) return p1.first < p2.first;else return p1.second > p2.second;}};unordered_map<string, int> word_cnt;priority_queue<pair<string, int>, vector<pair<string, int>>, Solution::mygreater> pq; // 小根堆vector<string> topKFrequent(vector<string>& words, int k) {// init word_cntfor(const auto& str:words){word_cnt[str]++;}// init pqfor(auto& e:word_cnt){pq.push(e);}while(pq.size() > k)pq.pop(); // init st// stack + vectr.push_back() 代替vector.insert(0, ...)降低时间复杂度stack<string> st;while(pq.size()){auto [str, cnt] = pq.top(); pq.pop();// auto&会有大bug， pop会改变str/cntst.push(str);}// init ansvector<string> ans;while(st.size()){string str = st.top(); st.pop();ans.push_back(str);}return ans;}
};4.数据流的中位数
link:295. 数据流的中位数 - 力扣（LeetCode）
思路：
大根堆记录[0, mid]
小根堆记录[mid+1, end]
中位数为： l.size==r.size ? (l.top()+r.top()) / 2.0 ? l.top()
tips
将pq.size() 和 int 比较时， 一定要将unsigned 转为int，不然会导致很多未定义行为
0u - 1u > 1为true：下溢（underflow）
code
class MedianFinder {
public:// 求中位数：大根堆+小根堆// lpq.size() >= rpqpriority_queue<int, vector<int>> lpq;//大根堆[0, mid]priority_queue<int, vector<int>, greater<int>> rpq;//小根堆[mid + 1, end]MedianFinder() {}void addNum(int num) {if(lpq.empty() || lpq.top() >= num) {lpq.push(num);}else rpq.push(num);// adjustwhile(int(lpq.size() - rpq.size()) > 1)// 一定要int（）{int out = lpq.top(); lpq.pop();rpq.push(out);}while(int(rpq.size() - lpq.size()) > 0)// 一定int（）{int out = rpq.top(); rpq.pop();lpq.push(out);}}double findMedian() {if((lpq.size() + rpq.size()) % 2 == 1) return lpq.top();else return (lpq.top() + rpq.top()) / 2.0;}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/
