C++标准库priority_queue自定义排序

比较函数

STL默认都是使用()比较的，默认比较使用less（即'<'运算符），如sort(a,a+n)，默认将数组按照递增的顺序来排序（前面的元素<后面），但是priority_queue<>默认是大根堆的，这是因为优先队列队首指向最后，队尾指向最前面的缘故！每次入队元素进去经排序调整后，优先级最大的元素排在最前面，也就是队尾指向的位置，这时候队首指向优先级最小的元素！所以虽然使用less但其实相当于greater，我们重载运算符的时候比较函数里面写>就相当于<排序方式。

实现方式

• 重写仿函数

class Solution {
public:

    struct compare {
        bool operator ()(const pair<int,int> &a, const pair<int,int> &b) {
            return a.second>b.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;        
        unordered_map<int, int> countMap;

        for (auto &item:nums) {
            countMap[item]++;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, compare> q;

        for (auto &[num, count]:countMap) {
            if (q.size()==k) {
                if (count>q.top().second) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }

        while (!q.empty()) {
            res.push_back(q.top().first);
            q.pop();
        }

        return res;
    }
};

• 自定义函数

class Solution {
public:
    static bool cmp(const pair<int,int> &a, const pair<int,int> &b)
    {
        return a.second>b.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;        
        unordered_map<int, int> countMap;

        for (auto &item:nums) {
            countMap[item]++;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(&cmp)> q(cmp);

        for (auto &[num, count]:countMap) {
            if (q.size()==k) {
                if (count>q.top().second) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }

        while (!q.empty()) {
            res.push_back(q.top().first);
            q.pop();
        }

        return res;
    }
};

• 重载运算符
  注意priority_queue默认使用less的比较函数，所以此处重载<运算符，如果使用greater的比较函数，则需重载>运算符。

class Solution {
public:
    struct Status {
        int val;
        int x;
        int y;

        bool operator < (const struct Status &rhs) const {
            return val > rhs.val;
        }
    };

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int row=matrix.size();
        int col=matrix[0].size();
        priority_queue<Status> q;

        for (int i=0;i<row;i++) {
            q.push({matrix[i][0], i, 0});
        }

        for (int i=0;i<k-1;i++) {
            auto f=q.top();
            q.pop();
            if (f.y<col-1) {
                q.push({matrix[f.x][f.y+1], f.x, f.y+1});
            }
        }

        return q.top().val;
    }
};