优先级队列（prioriry_queue)我们最常用于堆的排序中，其弹出元素的顺序并不是FIFO，而是根据优先级弹出，这个优先级最常见的就是根据大或小，当然还有我们自己定义的大或小。

我们在这里就不具体讲其底层结构了，主要还是介绍怎么用。

如何进行初始化？

prioriry_queue初始化是有三个参数（堆的类型，适配器，排序方法（仿函数））。

这个适配器就相当于是存放数据的媒介，一般为vector或deque（默认为vector）

在C++中，我们默认建的堆为大根堆：（以int为例）priority_queue<int> heap;但这实际是省略了后两个，写全了是priority_queue<int,vector<int>,less<int>)。

建小根堆就需要我们传仿函数了，也不难:priority_queue<int,vector<int>,greater<int>> heap;

有的时候，堆中建的并不是int，而是string char 甚至是pair，这时候C++提供的比较函数就不起作用了，需要我们自己写一个比较方法。（我们稍后在具体算法题中会实现）

我们用两道算法题介绍一下全部的用法

补充：使用此算法时极多数会有求TOPK问题，记住，求TOPK大用小根堆，TOPK小用大根堆。

class  KthLargest
{
  //求TOPK大用小根堆
   priority_queue<int ,vector<int>,greater<int>> heap;
   int _k;//

 
   public:
    KthLargest(int k,vector&<int> num)
    {
       _k=k;
       //把数全部插入堆中排序
       for(auto x:nums)
        {
            heap.push(x);
            if(heap.size()>_k)heap.pop();//我们要第k大，所以只要保证堆中元素有k个
                                         //此时堆顶自然就是第k大的
        }
    
     }
     
    int add(int val)
    {
       heap.push(val);
        if(heap.size()>_k)heap.pop(); //插入后排序返回堆顶
        return heap.top();
    }
};

第二题

这题也属于TOPK问题，但我们发现这题的比较条件有点特殊，首先要保证出现次数最多优先，次数相同的话，还要根据字典序输出，如果要照顾次数，我们当然是小根堆，照顾字典序，要用大根堆。

毕竟对比看来，次数相比的难度肯定低于字典序，因此我们建立一个大根堆。什么类型的堆呢？既要存放该字符串，又要记录次数，那么我们就需要用pair类型了。

同时，既要比较出现次数又要字典序排序，这种比较方法就需要我们自己实现然后作为仿函数传了。

class Solution {
    typedef pair<string,int> PSI;
    struct cmp
    {
        //仿函数就是在类内重载operator()
        bool operator()(const PSI&p1,const PSI&p2)
        {
            if(p1.second==p2.second)//当次数相同时再考虑字典序
            {
                return p1.first<p2.first;
            }
            return p1.second>p2.second;//不满足则次数优先
        }
    };


public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        //创建hash表，放入元素,记录出现次数
        unordered_map<string,int> hash;
        for(auto&s:words)
        {
            hash[s]++;
        }

        //创建堆并插入元素
        priority_queue<PSI,vector<PSI>,cmp> heap;
        for(auto&e:hash)
        {
            heap.push(e);
        }
         //我们只要前k个，原理和上一题相同
        while(heap.size()>k)
        {
            heap.pop();
        }
        
        //返回结果
        vector<string>ret(k);
        //这里选择逆序插入，因为每次插入的都是“最小的”
        //而我们输出的顺序是从大到小
        for(int i=k-1;i>=0;i--)
        {
            ret[i]=heap.top().first;
            heap.pop();
        }
        return ret;
    }
};