C priorityqueue
墨初 知识笔记 103阅读
今天我们来学习C中另一个容器适配器优先级队列——priority_queue和C一个重要组件仿函数
目录
一、priority_queue
1.1 priority_queue是什么
1.2 priority_queue的接口
1.2.1 priority_queue使用举例
二、仿函数
三、关于priority_queue的例题
四、模拟实现priority_queue
五、priority_queue的使用拓展
一、priority_queue 1.1 priority_queue是什么
priority_queue介绍文档priority_queue - C Reference (cplusplus.com)
优先队列priority_queue是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。
其底层就是堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。对于堆不熟悉的可以看到这里【精选】【数据结构初阶】树与二叉树——堆
优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。
底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类默认使用vector。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空、size()返回容器中有效元素个数 、front()返回容器中第一个元素的引用、push_back()在容器尾部插入元素、pop_back()删除容器尾部元素
标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector
需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap和pop_heap来自动完成此操作
1.2 priority_queue的接口
1.2.1 priority_queue使用举例
#include<iostream>#include<vector>#include<queue>#include<functional>using namespace std;int main(){priority_queue<int> q1;//大堆q1.push(5);q1.push(1);q1.push(10);q1.push(8);q1.push(7);while (!q1.empty()){cout<<q1.top()<< ;q1.pop();}cout << endl;priority_queue<int,vector<int>,greater<int>> q2;//小堆q2.push(5);q2.push(1);q2.push(10);q2.push(8);q2.push(7);while (!q2.empty()){cout << q2.top() << ;q2.pop();}return 0;}运行效果
我们可以看到构建一个小堆要用到仿函数下面我们来看看仿函数是个什么东西
二、仿函数
我们先来看到下面这段代码
struct ADD{int operator()(int x, int y){return x y;}};int main(){struct ADD add;cout << add(1,9) << endl;return 0;}运行效果
我们可以看到该段代码在结构体中实现了一个的运算符重载接着使用该结构体定义了一个对象add用该对象调用里面的运算符重载函数实现了一个功能这就是大名鼎鼎的仿函数
由此看来仿函数的本质就是的运算符重载使创建的对象可以像函数一样使用
三、关于priority_queue的例题
题目地址
215. 数组中的第K个最大元素
解题思路对于该使一个经典的top-k问题对于题我们可以先取k个数建立一个小堆再将后面的数依次与堆顶元素相比较如果比堆顶元素大就将堆顶元素丢弃后将该数入堆接着再接着与下一个数相比这样最终堆顶元素就是第K个最大的数了
解题代码
class Solution {public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int,vector<int>,greater<int>> q(nums.begin(),nums.begin()k); for(int ik;i<nums.size();i) { if(nums[i]>q.top()) { q.pop(); q.push(nums[i]); } } return q.top(); }};四、模拟实现priority_queue
下面我们来手搓一个priority_queue
#pragma once#include<iostream>#include<vector>#include<algorithm>namespace lhs{template<class T, class container std::vector<T>>class priority_queue{private:void adjustup(size_t child)//向上调整{while (child > 0){size_t parent (child - 1) / 2;if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child parent;}else break;}}void adjustdown(size_t parent)//向下调整{size_t child parent * 2 1;while (child < size()){if (child 1 < size() && _con[child] < _con[child 1]){child;}if (_con[parent] < _con[child]){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else break;}}public:void push(const T& x){_con.push_back(x);adjustup(size() - 1);}void pop(){std::swap(_con[0], _con[size() - 1]);_con.pop_back();adjustdown(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}private:container _con;};}测试代码
int main(){lhs::priority_queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(10);q.push(18);while (!q.empty()){std::cout << q.top() << ;q.pop();}std::cout << std::endl;return 0;}运行效果
但是上面手搓的priority_queue只能实现大堆的效果要实现小堆怎么办我们不可能手动修改代码中向上和向下调整函数中的判断符吧
这里就要轮到仿函数登场了
#pragma once#include<iostream>#include<vector>#include<algorithm>namespace lhs{template<class T>struct less{bool operator()(const T& x, const T& y){return x > y;}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x < y;}};template<class T, class container std::vector<T>, class compare less<T>>class priority_queue{private:void adjustup(size_t child)//向上调整{compare com;while (child > 0){size_t parent (child - 1) / 2;if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);child parent;}else break;}}void adjustdown(size_t parent)//向下调整{compare com;size_t child parent * 2 1;while (child < size()){if (child 1 < size() && com(_con[child 1], _con[child])){child;}if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else break;}}public:void push(const T& x){_con.push_back(x);adjustup(size() - 1);}void pop(){std::swap(_con[0], _con[size() - 1]);_con.pop_back();adjustdown(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}private:container _con;};}我们可以看到我们上面定义了两个仿函数less构建大堆和greater构建小堆我们在测试代码中传入我们所要选择的仿函数类型来控制大小堆的构建本质是通过不一样的仿函来控制运算符的改变
int main(){//lhs::priority_queue<int> q;//大堆lhs::priority_queue<int, std::deque<int>, lhs::greater<int>> q;//小堆q.push(1);q.push(2);q.push(3);q.push(4);q.push(10);q.push(18);while (!q.empty()){std::cout << q.top() << ;q.pop();}std::cout << std::endl;return 0;}运行效果
五、priority_queue的使用拓展
我们把之前写的日期类拿出来
class Date{friend ostream& operator<<(ostream& out, const Date& d);public:Date(int year, int month, int day);//构造函数int GetMonthDay(int year, int month) const;//获取year年month月的天数//运算符重载bool operator(const Date& d) const;//判断日期是否相同bool operator!(const Date& d) const;//判断日期是否不相同bool operator<(const Date& d) const;//判断当前日期是否在传入日期之前bool operator<(const Date& d) const;//判断当前日期是否在传入日期之前或相同bool operator>(const Date& d) const;//判断当前日期是否在传入日期之后bool operator>(const Date& d) const;//判断当前日期是否在传入日期之后或相同private:int _year;int _month;int _day;};int Date::GetMonthDay(int year, int month) const{int MonthDay[12] { 31,28,31,30,31,30,31,31,30,31,30,31 };//用数组来依次存储平年1到12月的天数if (month 2 && ((year % 4 0 && year % 100 ! 0) || year % 400 0))//判断是否为闰年的2月{return 29;}return MonthDay[month - 1];}Date::Date(int year, int month, int day){if (month < 1 || month>12 || (day<1 || day>GetMonthDay(year, month)))//判断日期是否合法{cout << Illegal date! << endl;}else{_year year;_month month;_day day;}}bool Date::operator(const Date& d) const{return _year d._year && _month d._month && _day d._day;}bool Date::operator!(const Date& d) const{return !(*this d);}bool Date::operator<(const Date& d) const{return _year < d._year || (_year d._year && _month < d._month) || (_year d._year && _month d._month && _day < d._day);}bool Date::operator<(const Date& d) const{return (*this < d) || (*this d);}bool Date::operator>(const Date& d) const{return !(*this < d);}bool Date::operator>(const Date& d) const{return !(*this < d);}ostream& operator<<(ostream& out, const Date& d){out << d._year << / << d._month << / << d._day << endl;return out;}下面我们可以使用priority_queue对自己写的日期类进行存储
int main(){Date d1(2022, 10, 23);Date d2(2022, 10, 25);Date d3(2022, 10, 24);priority_queue<Date> q1;q1.push(d1);q1.push(d2);q1.push(d3);cout << q1.top() << endl;priority_queue<Date,vector<Date>, greater<Date>> q2;q2.push(d1);q2.push(d2);q2.push(d3);cout << q2.top() << endl;return 0;}运行效果
因为我们自实现的Date重载了<和>运算符所以在我们使用priority_queue来存储时其内部会自动调用我们所写的运算符重载来构建大小堆
再看到下面的代码
int main(){priority_queue<Date*> q1;q1.push(new Date(2022, 10, 23));q1.push(new Date (2022, 10, 25));q1.push(new Date (2022, 10, 24));cout << *q1.top() << endl;return 0;}多次运行效果
咦怎么每次运行的结果都不一样
仔细看这里我们传入的存储类型是Date*而对于指针类型按默认的<和>运算符来比较这是比较指针所指向地址空间的大小但new创建空间时地址是随机的所以这是不合理的
下面我们来写两个仿函数实现一下Date*类型的比较
class Date_less{public:bool operator()(Date*a, Date* b){return *a < * b;}};class Date_greater{public:bool operator()(Date* a, Date* b){return *a > *b;}};int main(){priority_queue<Date*,vector<Date*>,Date_less> q1;priority_queue<Date*, vector<Date*>, Date_greater> q2;q1.push(new Date(2022, 10, 23));q1.push(new Date (2022, 10, 25));q1.push(new Date (2022, 10, 24));cout << *q1.top() << endl;q2.push(new Date(2022, 10, 23));q2.push(new Date(2022, 10, 25));q2.push(new Date(2022, 10, 24));cout << *q2.top() << endl;return 0;}在使用priority_queue时传入我们所写的仿函数就可以实现Date*类型的大小堆存储啦
综上所述泛型和运算符重载为我们提供了极大的方便我们如果对系统所提供的东西不满意就可以使用自己所定义的方法一切都自在掌控~