347. 前 K 个高频元素

347. 前 K 个高频元素

小顶堆：每个节点的值小于或等于孩子节点的值
堆在结构上符合完全二叉树的性质，存储上采用一维数组，利用下标来认亲。
可以使用优先队列实现大小顶堆
less 左数小于右数时，返回true，否则返回false
大顶堆实现时，若插入的数比根节点大，即优先队列内的左数全部小于插入的右数，返回true，右数向左移动。
小顶堆最小值在队头，最左边

#include<queue>
#include<vector>
#include<functional>
    priority_queue<int, vector<int>, greater<int>()> pq;  //小顶堆
    priority_queue<int> a; //大顶堆
    //等同于 priority_queue<int, vector<int>, less<int> > a;

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]

先用map统计nums中的数字和出现的频率
如何将map中的数据插入小顶堆
将

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
    //1.map记录元素出现的次数
        unordered_map<int,int>map;//两个int分别是元素和出现的次数
        for(auto& c:nums){
            map[c]++;
        }
    //2.利用优先队列，将出现次数排序
        //自定义优先队列的比较方式，小顶堆
        struct myComparison{
            bool operator()(pair<int,int>&p1,pair<int,int>&p2){
                return p1.second>p2.second;//小顶堆是大于号
            }
        };
        //创建优先队列
        priority_queue<pair<int,int>,vector<pair<int,int>>,myComparison> q;
        //遍历map中的元素
        //1.管他是啥，先入队列，队列会自己排序将他放在合适的位置
        //2.若队列元素个数超过k，则将栈顶元素出栈（栈顶元素一定是最小的那个）
        for(auto& a:map){
            q.push(a);
            if(q.size()>k){
               q.pop(); 
            }
        }
        //将结果导出
        vector<int>res;
        while(!q.empty()){
            res.emplace_back(q.top().first);
            q.pop();
        }
        return res;
    }
};