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

堆是一种二叉树的结构，有两种主要类型：最大堆和最小堆
下面附上之前写的两篇博客：
优先级队列(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();*/