宁波江北区城市建设档案馆网站,住房和规划建设局网站,wordpress 加一个form,服务专业的网页制作服务✨个人主页#xff1a; 北 海 #x1f389;所属专栏#xff1a; C修行之路 #x1f383;操作环境#xff1a; Visual Studio 2019 版本 16.11.17 文章目录 #x1f307;前言#x1f3d9;️正文1、优先级队列的使用1.1、基本功能1.2、优先级模式切换1.3、相关题目 2、模拟… ✨个人主页 北 海 所属专栏 C修行之路 操作环境 Visual Studio 2019 版本 16.11.17 文章目录 前言️正文1、优先级队列的使用1.1、基本功能1.2、优先级模式切换1.3、相关题目 2、模拟实现优先级队列2.1、构造函数2.2、基本功能2.3、仿函数的使用2.4、特殊场景 3、源码 总结 前言
优先级队列 priority_queue 是容器适配器中的一种常用来进行对数据进行优先级处理比如优先级高的值在前面这其实就是初阶数据结构中的 堆它俩本质上是一样东西底层都是以数组存储的完全二叉树不过优先级队列 priority_queue 中加入了 泛型编程 的思想并且属于 STL 中的一部分 这就是一个堆最顶上的石头 优先级最高 或 优先级最低 ️正文
1、优先级队列的使用
首先需要认识一下优先级队列 priority_queue 1.1、基本功能
优先级队列的构造方式有两种直接构造一个空对象 和 通过迭代器区间进行构造 直接构造一个空对象
#include iostream
#include vector
#include queue //注意优先级队列包含在 queue 的头文件中using namespace std;int main()
{priority_queueint pq; //直接构造一个空对象默认为大堆cout typeid(pq).name() endl; //查看类型return 0;
}注意 默认比较方式为 less最终为 优先级高的值排在上面大堆
通过迭代器区间构造对象
#include iostream
#include vector
#include queue //注意优先级队列包含在 queue 的头文件中using namespace std;int main()
{vectorchar vc { a,b,c,d,e };priority_queuechar, dequechar, greaterchar pq(vc.begin(), vc.end()); //现在是小堆cout typeid(pq).name() endl; //查看类型cout endl;while (!pq.empty()){//将小堆中的堆顶元素依次打印cout pq.top() ;pq.pop();}return 0;
}注意 将比较方式改为 greater 后生成的是 小堆并且如果想修改比较方式的话需要指明模板参数2 底层容器因为比较方式位于模板参数3不能跳跃缺省遵循缺省参数规则 测试数据27,15,19,18,28,34,65,49,25,37 分别生成大堆与小堆 大堆
vectorint v { 27,15,19,18,28,34,65,49,25,37 };
priority_queueint, vectorint, lessint pq(v.begin(), v.end());
//priority_queueint pq(v.begin(), v.end()); //两种写法结果是一样的默认为大堆小堆
vectorint v { 27,15,19,18,28,34,65,49,25,37 };
priority_queueint, vectorint, greaterint pq(v.begin(), v.end()); //生成小堆接下来使用优先级队列以大堆为例中的各种功能入堆、出堆、查看堆顶元素、查看堆中元素个数 #include iostream
#include vector
#include queue //注意优先级队列包含在 queue 的头文件中using namespace std;void Print(const priority_queueint pq)
{cout 是否为空 pq.empty() endl;cout 堆中的有效元素个数 pq.size() endl;cout 堆顶元素 pq.top() endl;cout endl;
}int main()
{vectorint v { 27,15,19,18,28,34,65,49,25,37 };priority_queueint pq(v.begin(), v.end()); //默认生成大堆Print(pq);pq.push(10);pq.push(100);Print(pq);pq.pop();pq.pop();pq.pop();Print(pq);return 0;
}1.2、优先级模式切换
创建优先级队列时默认为 大堆因为比较方式仿函数缺省值为 less这个设计比较反人类小于 less 是大堆大于 greater 是小堆…
如果想要创建 小堆需要将比较方式仿函数改为 greater
注意 因为比较方式仿函数 位于参数3而参数2也为缺省参数因此如果想要修改参数3就得指明参数2
讲人话就是想改变比较方式的话需要把参数2也写出来这个设计也比较反人类明明只改一个比较方式为什么要写明底层容器…
priority_queueint pqBig; //大堆
priority_queueint, vectorint, greaterint pqSmall; //小堆1.3、相关题目
优先级队列堆可以用来进行排序和解决 Top-K 问题比如 查找第 k 个最大的值 就比较适合使用优先级队列
215. 数组中的第K个最大元素 思路利用数组建立大小为 k 的小堆将剩余数据与堆顶值比较如果大于就入堆
为什么建小堆因为此时需要的是最大的值建大堆可能会导致次大的值无法入堆
#include queueclass Solution {
public:int findKthLargest(vectorint nums, int k) {//建堆priority_queueint, vectorint, greaterint pq(nums.begin(), nums.begin() k);//将剩余元素判断入堆auto it nums.begin() k;while(it ! nums.end()){if(*it pq.top()){pq.pop(); //出小的值pq.push(*it); //入大的值}it;}//此时的堆顶元素就是第 k 个最大元素return pq.top();}
};优先级队列非常适合用来解决类似问题 2、模拟实现优先级队列
优先级队列 priority_queue 属于容器适配器的一种像栈和队列一样没有迭代器同时也不需要实现自己的具体功能调用底层容器的功能就行了不过因为堆比较特殊需要具备 向上调整 和 向下调整 的能力确保符合堆的规则
2.1、构造函数
注 现在实现的是没有仿函数的版本
优先级队列的基本框架为
#pragma once#include vectornamespace Yohifo
{//默认底层结构为 vectortemplateclass T, class Container std::vectorTclass priority_queue{public://构造函数及其他功能private:Container _con; //其中的成员变量为底层容器对象};
}默认构造函数显式调用底层结构的默认构造函数
//默认构造函数
priority_queue():_con()
{}迭代器区间构造将区间进行遍历逐个插入即可
//迭代器区间构造
templateclass InputIterator
priority_queue(InputIterator first, InputIterator last):_con()
{while (first ! last){push(*first);first;}
}测试 2.2、基本功能
因为是容器适配器所以优先级队列也没有迭代器
同时基本功能也比较少首先来看看比较简单的容量相关函数 容量相关 判断是否为空复用底层结构的判空函数
//判断是否为空
bool empty() const
{return _con.empty();
}获取优先级队列大小复用获取大小的函数
//优先级队列的大小有效元素数
size_t size() const
{return _con.size();
}获取堆顶元素堆顶元素即第一个元素完全二叉树的根
//堆顶元素优先级最 高/低 的值
const T top() const
{return _con.front();
}注意 以上三个函数均为涉及对象内容的改变因此均使用 const 修饰 this 指针所指向的内容 数据修改 因为在插入/删除数据后需要确保堆能符合要求
大堆父节点比子节点大小堆父节点比子节点小
因此每进行一次数据修改相关操作都需要检查当前堆结构是否被破坏这一过程称为 调整
插入数据尾插数据然后向上调整
//插入数据
void push(const T val)
{//直接尾插然后向上调整_con.push_back(val);adjust_up(size() - 1); //从当前插入的节点处进行调整
}向上调整将当前子节点与父节点进行比较确保符合堆的特性如果不符合需要进行调整
//向上调整
void adjust_up(size_t child)
{size_t parent (child - 1) / 2;while (child ! 0){//父 子 此时为大堆如果不符合则调整if (_con[child] _con[parent]){std::swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}注意 如果在调整过程中发现遵循堆的特性那么此时不需要再调整直接 break 即可
删除数据将堆顶数据交换至堆底删除堆底元素再向下调整堆
//删除堆顶元素优先级最 高/低 的值
void pop()
{if (empty()) return;//将堆顶元素交换至堆底删除向下调整std::swap(_con.front(), _con.back());_con.pop_back();adjust_down(0);
}向下调整将当前父节点与 【较大 / 较小】 子节点进行比较确保符合堆的特性如果不符合需要进行调整
//向下调整
void adjust_down(size_t parent)
{size_t child parent * 2 1; //假设左孩子为 【大孩子 / 小孩子】while (child size()){//判断右孩子是否比左孩子更符合条件如果是则切换为与右孩子进行比较if (child 1 size() _con[child 1] _con[child])child;//父 子 此时为大堆如果不符合则调整if (_con[child] _con[parent]){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}elsebreak; //满足条件时一样需要跳出不再调整}
}注意 删除时需要先判断当前堆是否为空空则不执行删除
测试 假设先使用 小堆需要将下图中的三处逻辑判断改为 难道每次使用时都得手动切换吗而且如果我想同时使用大堆和小堆时该怎么办
答案是没必要通过 仿函数 可以轻松解决问题这也是本文的重点内容
2.3、仿函数的使用
仿函数又名函数对象 function objects仿函数的主要作用是 借助类和运算符重载做到同一格式兼容所有函数 这有点像函数指针相比于函数指针又长又难理解的定义仿函数的使用可谓是很简单了
下面是两个仿函数作用是比较大小
templateclass T
struct less
{//比较 是否小于bool operator()(const T x, const T y){return x y;}
};templateclass T
struct greater
{//比较 是否大于bool operator()(const T x, const T y){return x y;}
};此时 priority_queue 中的模板参数升级为3个而参数3的缺省值就是 less
templateclass T, class Container std::vectorT, class Comper lessT当需要进行逻辑比较时大小堆需要不同的比较逻辑只需要调用 operator() 进行比较即可
这里采用的是匿名对象调用的方式当然也可以直接实例化出一个对象然后再调用 operator() 进行比较
在使用仿函数后向上调整 和 向下调整 变成了下面这个样子
//向上调整
void adjust_up(size_t child)
{size_t parent (child - 1) / 2;while (child ! 0){//父 子 此时为大堆如果不符合则调整if (Comper()(_con[parent], _con[child])) //Comper() 为匿名对象{std::swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}//向下调整
void adjust_down(size_t parent)
{size_t child parent * 2 1; //假设左孩子为 【大孩子 / 小孩子】while (child size()){//判断右孩子是否比左孩子更符合条件如果是则切换为与右孩子进行比较//同样使用匿名对象if (child 1 size() Comper()(_con[child], _con[child 1]))child;//父 子 此时为大堆如果不符合则调整if (Comper()(_con[parent], _con[child])) //匿名对象调用 operator(){std::swap(_con[child], _con[parent]);parent child;child parent * 2 1;}elsebreak; //满足条件时一样需要跳出不再调整}
}使用仿函数后可以轻松切换为小堆 注意 为了避免自己写的仿函数名与库中的仿函数名起冲突最好加上命令空间访问指定域中的仿函数
仿函数作为 STL 六大组件之一处处体现着泛型编程的思想 仿函数给我们留了很大的发挥空间只要我们设计的仿函数符合调用规则那么其中的具体比较内容可以自定义后续在进行特殊场景的比较时作用很大
2.4、特殊场景
假设此时存在 日期类部分
class Date
class Date
{
public:Date(int year 1970, 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 std::ostream operator(std::ostream _cout, const Date d){_cout d._year - d._month - d._day;return _cout;}
private:int _year;int _month;int _day;
};创建数据为 Date 的优先级队列大堆取堆顶元素判断是否能对自定义类型进行正确调整
void TestPriorityQueue3()
{Yohifo::priority_queueDate q1;q1.push(Date(2012, 3, 11));q1.push(Date(2012, 3, 12));q1.push(Date(2012, 3, 13));cout q1.top() endl; //取堆顶元素
}结果正确因为在实际比较时调用的是 Date 自己的比较逻辑所以没问题 但如果此时数据为 Date*再进行比较
void TestPriorityQueue4()
{//数据类型为指针Yohifo::priority_queueDate* q1·;q1.push(new Date(2012, 3, 11));q1.push(new Date(2012, 3, 12));q1.push(new Date(2012, 3, 13));cout *(q1.top()) endl;
}结果错误多次运行结果不一样因为此时调用的是指针的比较逻辑地址是随机的因此结果也是随机的 解决方法
通过再编写指针的仿函数解决通过模板特化解决
这里介绍法1法2在下篇文章《模板进阶》中讲解
仿函数给我们提供了极高的自由度因此可以专门为 Date* 编写一个仿函数曲线救国
//小于
templateclass T
struct pDateLess
{bool operator()(const T p1, const T p2){return (*p1) (*p2);}
};//大于
templateclass T
struct pDateGreater
{bool operator()(const T p1, const T p2){return (*p1) (*p2);}
};在构建对象时带上对对应的 仿函数 就行了
void TestPriorityQueue5()
{//数据类型为指针Yohifo::priority_queueDate*, vectorDate*, pDateLessDate* qBig;qBig.push(new Date(2012, 3, 11));qBig.push(new Date(2012, 3, 12));qBig.push(new Date(2012, 3, 13));cout *(qBig.top()) endl;Yohifo::priority_queueDate*, vectorDate*, pDateGreaterDate* qSmall;qSmall.push(new Date(2012, 3, 11));qSmall.push(new Date(2012, 3, 12));qSmall.push(new Date(2012, 3, 13));cout *(qSmall.top()) endl;
}此时无论是 大堆 还是 小堆 都能进行正常比较 关于 Date* 仿函数的具体调用过程可以自己下去通过调试观察 3、源码
本文中提及的所有源码都在此仓库中 《优先级队列博客》 总结
以上就是本次关于 C STL学习之【优先级队列】的全部内容了在本文中我们又学习了一种容器适配器 priority_queue优先级队列在对大量数据进行 Top-K 筛选时优势是非常明显的因此需要好好学习尤其是向上调整和向下调整这两个重点函数最后我们还见识了仿函数的强大之处容器在搭配仿函数后能做到更加灵活适应更多需求 相关文章推荐 STL 之 适配器 C STL学习之【反向迭代器】 C STL学习之【容器适配器】 STL 之 list C STL学习之【list的模拟实现】 C STL学习之【list的使用】 STL 之 vector C STL学习之【vector的模拟实现】 C STL学习之【vector的使用】
