这盘博客记录了关于优先级队列的几道题，包括最后一块石头的重量、数据流中的第K大元素、前K个高频单词、数据流的中位数。
class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for(auto s : stones) heap.push(s);while(heap.size() > 1){int x = heap.top();heap.pop();int y = heap.top();heap.pop();if(x > y) heap.push(x-y);}return heap.size() ? heap.top():0;}
};思路分析：这道题先要创建一个大根堆，将所给数组中的每一个值放入大根堆，堆顶的就是重量最大的，依次得到两个堆顶的元素，将它们相减，如果相减后不为0，那么将差值放到堆里。再次取两次堆顶的元素，重复上述过程，直到堆里元素个数≤1。
class KthLargest {priority_queue<int, vector<int>, greater<int>> _p;int _k;
public:KthLargest(int k, vector<int>& nums):_k(k) {for(auto e : nums){_p.push(e);if(_p.size() > _k) _p.pop();}}int add(int val) {_p.push(val);if(_p.size() > _k) _p.pop();return _p.top();}
};题目分析：这道题是要得到数据流中的第K大元素，也就是和TopK问题相关，所以要建立一个大小为K的小堆。将数据流里的元素依次插入到小堆，在插入一个元素之后，堆顶元素就是第K大元素。
class Solution {using PSI = pair<string, int>;
public:struct cmp{bool operator()(const PSI& p1, const PSI& p2){if(p1.second == p2.second) return p1.first < p2.first; //频次相同，按照大根堆的方式排序return p1.second > p2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {//1.统计一下每个单词的频次unordered_map<string, int> hash;for(auto& e : words) hash[e]++;//2.创建一个大小为k的堆priority_queue<PSI, vector<PSI>, cmp> heap;//3.TopK的主逻辑for(auto e : hash){heap.push(e);if(heap.size() > k) heap.pop(); }//4.提取结果vector<string> ret(k);for(int i = k-1 ; i >=0 ; i--){ret[i] = heap.top().first;heap.pop();}return ret; }
};题目分析：首先创建一个哈希表hash<string,int>，把单词列表中的每一个单词放到哈希表中。创建一个大小为k的堆，堆中的cmp方法先比较频次，频次相同则比较字母序。遍历这个哈希表，将哈希表中的元素依次这个放入堆里，最后得到的堆就是所要的K个，并将他们逆序放在一个vector里。
class MedianFinder
{
private: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() {int m = _left.size();int n = _right.size();if(m == n) return (_left.top() + _right.top())/2.0;else return _left.top();}
};
题目分析：这道题有三种思路：
1.直接sort，来一个值排序一次，sort的时间复杂度为O(nlogn)，find时直接根据数组下标查找即可，为O(1)。但是这种方法会超时。
2.采用插入排序，每次进来插入一个数就进行插入，时间复杂度为O(N)，find时也只需要根据数组下标查找，为O(1)。
3.大小堆来维护数据流的中位数，我们创建一个大堆_left和一个小堆_right，其大小分别是m和n，我们需要维护这样一个规则：m==n，或m=n+1。通过取两个堆的堆顶元素之和/2或_left堆顶元素，得到中位数。我们需要处理一个细节问题，就是在新数num来的时候，加到哪个堆上呢？这里需要分类讨论,，设x为_left栈顶元素：
1）m==n ,
如果num <= x 或 m == 0，把num直接放到_left；如果num > x，把num先放到_right，然后把_right的top放到_left，_right栈顶元素出栈。
2）m=n+1
如果num <= x，先把num放到_left，然后再把_left的top放到_right，_left的栈顶元素出栈；如果num > x，直接把num放到_right。