必威体育Betway必威体育官网
当前位置:首页 > IT技术

priority_queue特性解读

时间:2019-07-02 03:44:34来源:IT技术作者:seo实验室小编阅读:57次「手机版」
 

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;
    }
};

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读