烟台网站建设方案报价,可以自己做网站的网址,wordpress 搜索乱码,企业信息登记号查询系统⭐博客主页#xff1a;️CS semi主页 ⭐欢迎关注#xff1a;点赞收藏留言 ⭐系列专栏#xff1a;C初阶 ⭐代码仓库#xff1a;C初阶 家人们更新不易#xff0c;你们的点赞和关注对我而言十分重要#xff0c;友友们麻烦多多点赞#xff0b;关注#xff0c;你们的支持是我… ⭐博客主页️CS semi主页 ⭐欢迎关注点赞收藏留言 ⭐系列专栏C初阶 ⭐代码仓库C初阶 家人们更新不易你们的点赞和关注对我而言十分重要友友们麻烦多多点赞关注你们的支持是我创作最大的动力欢迎友友们私信提问家人们不要忘记点赞收藏关注哦 priority_queue优先级队列 前言一、priority_queue的介绍二、priority_queue的使用三、OJ题数组中的第K个最大元素1题目描述2解题思路3解题代码 四、priority_queue模拟实现存于gittee代码仓库五、仿函数1、引子2、实践于优先队列模拟实现 前言
优先级队列放在这里进行单独讲解是不同于前面的队列和栈的它所运用到的数据结构中的知识很多需要用到堆的知识。 一、priority_queue的介绍 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 pop_back()删除容器尾部元素标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。 二、priority_queue的使用
默认类型
#includeiostream
#includequeue
#includevector
using namespace std;int main()
{// 默认是大堆 也就是降序//priority_queueint pq;// 仿函数控制实现小堆 也就是升序priority_queueint, vectorint, greaterint pq;pq.push(4);pq.push(1);pq.push(3);pq.push(5);pq.push(2);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;return 0;
}自定义类型
#includeiostream
#includequeue
#includevector
using namespace std;class Date
{
public:Date(int year 1900, int month 1, int day 1): _year(year), _month(month), _day(day){}bool 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 operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}friend ostream operator(ostream _cout, const Date d){_cout d._year - d._month - d._day;return _cout;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{// 大堆需要用户在自定义类型中提供的重载priority_queueDate q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout q1.top() endl;// 如果要创建小堆需要用户提供的重载priority_queueDate, vectorDate, greaterDate q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout q2.top() endl;
}int main()
{TestPriorityQueue();return 0;
}三、OJ题
数组中的第K个最大元素
1题目描述 2解题思路
方法一先利用优先级队列将其建成大堆然后再利用循环将前k-1个元素都pop出去再输出顶部的数据就为题解。
方法二建成小堆将k个元素先放到堆里面去再遍历后面的数比顶元素大的值替换它直到最后一个最终栈顶的元素就是k大的数。这样的时间复杂度很低。
3解题代码
class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint pq(nums.begin(), nums.end());while(--k){pq.pop();}return pq.top();}
};class Solution {
public:int findKthLargest(vectorint nums, int k) {// 建小堆priority_queueint, vectorint, greaterint pq(nums.begin(), nums.begin() k);for(int i k; i nums.size(); i){if(nums[i] pq.top()){pq.pop();pq.push(nums[i]);}}// 找到第二大的数return pq.top();}
};四、priority_queue模拟实现存于gittee代码仓库
priority_queue.h
#pragma oncetemplateclass T
class Less
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
};
namespace JRH
{templateclass T, class container vectorint, class Compare LessTclass priority_queue{private:void AdjustDown(int parent){// 利用仿函数以及库里面的less函数Compare com;// 找左右孩子大的那个int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child], _con[child 1])){child;}// 判断孩子和父亲哪个大孩子大交换if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}void AdjustUp(int child){Compare com;int parent (child - 1) / 2;while (child 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}public:priority_queue(){}// 构造函数templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last){while (first ! last){_con.push_back(*first);first;}// 建堆for (int i (_con.size() - 1 - 1) / 2; i 0; i--){AdjustDown(i);}}// 删除void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}// 插入void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);}// 取堆顶元素const T top(){return _con[0];}// 判空bool empty(){return _con.empty();}// 算元素个数size_t size(){return _con.size();}private:container _con;};void test_priority_queue(){// 默认是大堆priority_queueint, vectorint, Greaterint pq;pq.push(4);pq.push(1);pq.push(3);pq.push(5);pq.push(2);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;}
}
test.cpp:
#includeiostream
#includequeue
#includevector
using namespace std;#includepriority_queue.hint main()
{JRH::test_priority_queue();return 0;
}五、仿函数
1、引子 也可以加一个类模板
2、实践于优先队列模拟实现
这样子其实仿函数更加好理解了我们利用一个自己写的或者是库里面写的都可以利用仿函数我们的和就没那么刻板了我们利用仿函数让它们比较进入到我们规定的区域内进行比较即可。
