优先级队列
priority_queque
优先级队列的底层是堆（二叉树的堆）
第二个参数容器适配器，第三个参数仿函数，less是大的优先级高
后面俩个参数给缺省值，测试优先级队列，默认大的优先级高
也可以用一个区间去初始化
把第三个参数改为greater，就是小的优先级高
习题
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> pq(nums.begin(),nums.end()); while(--k) { pq.pop(); } return pq.top(); } };
215. 数组中的第K个最大元素 - 力扣（LeetCode）
优先级队列模拟实现
namespace myspace { //大堆 template<class T,class Container=vector<T>> class priority_queque { public: template<class InputerIterator> priority_queque(InputerIterator first, InputerIterator last)//迭代器区间 { while (first < last) { _con.push_back(*first); ++first; } //建堆 for (int i = (_con.size() - 1 - 1)/2;i>=0;--i) { adjust_down(i); } }priority_queque()//默认构造，不然会报错，因为上面的迭代器区间这个函数跟构造函数同名 {} void adjust_up(size_t child) { size_t parent = (child - 1) / 2; while (child>0) { if (_con[parent] < _con[child]) { std::swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && _con[child + 1] > _con[child]) { ++child; } //选出最大的孩子 if (_con[child] > _con[parent]) { std::swap(_con[child],_con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& x)//（大堆）堆的插入 { _con.push_back(x); adjust_up(_con.size()-1);//尾插后向上跳转 } void pop()//删除堆顶数据 { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); }//对顶数据和最后一个数据交换，之后删除最后一个数据，然后向下调整堆 const T& top() { return _con[0]; } bool empty() { return _con.empty(); } size_t size()const { return _con.size(); } private: Container _con; }; } int main() { int a[]= { 156,132,156,156,31,5,15,31,364,15 }; myspace::priority_queque<int> pq(a,a+sizeof(a)/sizeof(int)); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } return 0; }
优先级队列要控制比较大小的逻辑，上面的写法我们以大堆为例但是这样把优先级队列给写死了，如果把里面的>改为<则会变成小堆，但是这样比较麻烦。上面我们只传了俩个参数，还有一个参数没传，第三个参数是仿函数
仿函数
仿函数/函数对象——是个类，重载的是operator（），类对象可以像函数一样去使用，本质就是重载
（）也是一个运算符
跟sort不同，sort传的是函数模板，传的是对象，而这里传的是类模板 ，传的是类型
这里的lsFunc不是函数名 ，而是一个类对象
这俩个等价
不仅有less，还有greater
namespace myspace { template<class T> class less { public: bool operator()(const T& l, const T& r)const { return l < r; } }; template<class T> class greater { public: bool operator()(const T& l, const T& r)const { return l > r; } }; }
我们将这里全部改成小于号
传入仿函数
这样就可以去替换小于号
小堆
大堆
完整代码
namespace myspace { //大堆 template<class T,class Container=vector<T>,class Compare=less<T>> class priority_queque { public: template<class InputerIterator> priority_queque(InputerIterator first, InputerIterator last)//迭代器区间 { while (first < last) { _con.push_back(*first); ++first; }
