priority
priority_queue是优先级队列的意思，简单理解就是队列带有了优先级的区分，和平常我们看到的队列queue的区别在于，平时的队列元素没有优先之分，先进来的数据先出去，而通常情况下，在一些实际的场景中，队列往往设有优先级之分，这在计算机网络中是非常常见的，举个例子，当一个非常重要的数据进入队列之后，需要快速发出去，就需要让其他数据等待，重要的数据先发出去，这就要求该数据有高于其他数据的优先级标识。而优先级队列也正是这样的原理。
优先级队列的用处很广泛，用法也很灵活我就简单的场景来描述优先级队列的特性：
优先级队列的定义：
#include <iOStream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main()
{
priority_queue <int, vector<int>, greater<int>> pq1;
priority_queue <int, vector<int>, less<int>> pq2;
for (int i=0; i<8; ++i) {
pq1.push(i);
pq2.push(i);
}
cout << "pq1: ";
while (!pq1.empty()) {
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
cout << "pq2: ";
while (!pq2.empty()) {
cout << pq2.top() << " ";
pq2.pop();
}
cout <<endl;
return 0;
}
运行结果是：
从上面可以看出，greater是从小到大排列，让小的元素优先出队列，而less是从大到小排列，让大的元素优先出队列。这是队列的基本用法，也是比较常用的，但其实，优先级队列的用法非常灵活，less和greater是可以重载的，而且除了int这些基本的数据类型外，还可以装载其他数据类型。一个类，一个数据对等。举个例子。
代码如下：
auto cmp = [](const pair<int,int>& a, const pair<int,int>& b){
return a.second < b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>, cmp>;
这就是将类似于将一个key-value键值对存入其中，并且用value的值来做优先级的标定。一般情况是，当满足条件时，输入参数的第一个参数在队列中的优先级要高，换句话说，在pop的时候，上述情况下，小的元素要率先被拿出来。因此基于以上特性，优先级队列的第一次使用实在leetcode 347. Top K Frequent Elements 题目中使用，下面是我参考高手思路的AC代码：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
if (!k) {
return res;
}
unordered_map<int, int> numsmap;
for (auto num : nums) {
++numsmap[num];
}
auto cmp = [](const pair<int,int>& a, const pair<int,int>& b){
return b.second > a.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (auto ans : numsmap) {
pq.push(make_pair(ans.first, ans.second));
}
while (k) {
res.push_back(pq.top().first);
pq.pop();
--k;
}
return res;
}
};
两外也可以使用priority_queue来做类的优先级标定处理。
在leetcode 778. Swim in Rising Water题目中，使用了相应的特性：
class Tuple {
public:
Tuple(int r, int c, int v) : row(r), col(c), val(v) {}
int row, col, val;
};
/*struct cmp {
bool operator()(const Tuple& a, const Tuple& b) {
return a.val > b.val;
}
};*/
class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
if (grid.size() < 1 && grid[0].size() < 1) {
return 0;
}
auto cmp = [] (const Tuple& a, Tuple& b) {
return a.val > b.val;
};
int res=0;
int gridsize = grid.size();
vector<vector<bool> > visited(gridsize, vector<bool> (gridsize, false));
priority_queue<Tuple, vector<Tuple>, decltype(cmp)> pq(cmp);
pq.push(Tuple(0, 0, grid[0][0]));
visited[0][0] = 1;
while (!pq.empty()) {
int row = pq.top().row, col = pq.top().col, val = pq.top().val;
pq.pop();
res = max(res, val);
if (row == gridsize-1 && col == gridsize-1) {
return res;
}
if (row-1 >= 0 && !visited[row-1][col]) {
visited[row-1][col] = 1;
pq.push(Tuple(row-1, col, grid[row-1][col]));
}
if (row+1 < gridsize && !visited[row+1][col]) {
visited[row+1][col] = 1;
pq.push(Tuple(row+1, col, grid[row+1][col]));
}
if (col-1 >= 0 && !visited[row][col-1]) {
visited[row][col-1] = 1;
pq.push(Tuple(row, col-1, grid[row][col-1]));
}
if (col+1 < gridsize && !visited[row][col+1]) {
visited[row][col+1] = 1;
pq.push(Tuple(row, col+1, grid[row][col+1]));
}
}
return -1;
}
};