c++ 小顶堆 大顶堆的实现 （基于优先队列）

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性，包括基本操作

和队列基本操作相同:

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

定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
LC 347 最高频的前   K 个元素 ，可以使用小根堆实现的优先队列，实现nlogn以下的时间复杂度

class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }  //通过仿函数重载()实现一个专门比较用的类
    };
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
    for(int i =0;i < nums.size(); i++){
            mp[nums[i]]++;
        }
     priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> por_que;
    for(auto it=mp.begin();it!=mp.end();it++){
        por_que.emplace(*it);
        if(por_que.size() > k)
            por_que.pop();
    }
        vector<int>result(k);
    for(int i=k-1;i>=0;i--){
        result[i]=por_que.top().first;
        por_que.pop();
    }
    return result;

    }
};