[数据结构与算法]C++优先队列

优先队列实际上是堆

根节点的值比所有节点值都大，称为最大堆；

根节点的值比所有节点值都小，称为最小堆；

基本操作：

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

第一种用法：

priority_queue<int> q1;//默认从大到小排序，整数中元素大的优先级高 

第二种用法：

//升序队列 大顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列 小顶堆
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

第三种用法自定义：

struct cmp{
    bool operator()(pair<int,int> m , pair<int,int>n){
        return m.second > n.second;
    }
};
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
    }
};

简单例题：347. 前 K 个高频元素 - 力扣（LeetCode） (leetcode-cn.com)

?

基本思想：

? ? ? ? 维护一个小顶堆，如果size() < k 则进入，如果size（） == k 时，当堆顶小于当前次数大小，则弹出队头，该次数入队

struct cmp{
    bool operator()(pair<int,int> m , pair<int,int>n){
        return m.second > n.second;
    }
};
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        int n = nums.size() , x = 0;
        if(n == 1) return nums;
        unordered_map<int,int>map;
        for(auto x : nums)map[x]++;

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

        for(auto &[num,count] : map){
            if(q.size() == k){
                if(q.top().second < count){
                    q.pop();
                    q.push({num , count});
                }
            } else{
                q.push({num , count});
            }
        }
        vector<int>res;
        while (!q.empty()){
            res.emplace_back(q.top().first);
            q.pop();
        }
        return res;
    }
};

?