C++ priority_queue使用方法

以leetcode 1081题为例，https://leetcode.cn/problems/number-of-orders-in-the-backlog/

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        // 新增sell订单，找buy的大于sell的，找buy最大值
        // 新增buy订单，找sell的小于buy的，找sell最小值
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> sell; // [price, amount]
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> buy; 
        for (auto od : orders) {
            if (od[2] == 0) { // buy
                while (!sell.empty() && od[1] > 0 && sell.top().first <= od[0]) {
                    if (od[1] >= sell.top().second) {
                        od[1] -= sell.top().second;
                        sell.pop();
                    } else {
                        int price = sell.top().first;
                        int amount = sell.top().second-od[1];
                        sell.pop();
                        sell.push({price, amount});
                        od[1] = 0;
                    }
                }
                if (od[1] != 0) {
                    buy.push({od[0], od[1]});
                }
                
            } else {  // sell
                while (!buy.empty() && od[1] > 0 && buy.top().first >= od[0]) {
                    if (od[1] >= buy.top().second) {
                        od[1] -= buy.top().second;
                        buy.pop();
                    } else {
                        int price = buy.top().first;
                        int amount = buy.top().second-od[1];
                        buy.pop();
                        buy.push({price, amount});
                        od[1] = 0;
                    }
                }
                if (od[1] != 0) {
                    sell.push({od[0], od[1]});
                }
            }
        }
        int MOD = 1000000007;
        int total = 0;
        while (!buy.empty()) {
            total = (total + buy.top().second) % MOD;
            buy.pop();
        }
        while (!sell.empty()) {
            total = (total + sell.top().second) % MOD;
            sell.pop();
        }
        return total;
    }
};

priority_queue的模版类接收三个参数，第一个是类型，第二个是容器，第三个是比较函数类，其中后两个有默认值。

template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> class priority_queue

容器默认是vector，比较类默认是less<T>，也就是自定义比较函数中从小到大排列，可以认为是数值越大，优先级越高，也就是从小到大排序后的最后一个元素为队首。反之，greater<T>则是最小值优先级最高。可以从上面的 greater<pair<int, int>> 和 less<pair<int, int>> 看出，buy队列要找的优先级高的是最大值，使用less<T>。

可以自己写比较类，如下：

class cmp {
public:
    bool operator()(const pair<int, int>& x1, const pair<int, int>& x2) {
        return x1.second > x2.second;
    }
};

这个比较类实现按照pair的second越小的优先级越高（我是这么记忆的，上述比较类实现了排序函数从大到小排列，优先级队列是取排序后排在最后的作为优先级最高）。注意使用emplace和使用push的区别。另外，在使用的时候cmp后面不需要加括号，传入的类型是作为一个类，而不是一个类的实例，与自定义排序函数有区别。

int main() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
    q.emplace(1, 4);
    q.push({2, 3});
    q.emplace(3, 2);
    cout << q.top().first << endl;
    q.pop();
    cout << q.top().first << endl;
    q.pop();
    cout << q.top().first << endl;
    q.pop();
    return 0;
}

所以上面的代码输出为

3
2
1

除此之外，还可以对元素重载小于号（<）运算符，这样就不需手动传入比较类，可以使用less<T>或greater<T>来自动实现。详细方法参阅之前写的自定义比较函数那一篇：https://www.cnblogs.com/roadwide/p/16139272.html

有一点需要注意，队列内的元素值不能更改，因为是const类型的。如果需要更改，应该先储存元素的值，再进行pop，更改后再push进去。

原文链接: https://www.cnblogs.com/roadwide/p/17019771.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/309093

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C++ priority_queue使用方法

相关推荐