建设php网站,网站优化公司大家好,WordPress如何添加cnzz,国内正规seo网络推广文章目录 补充知识#xff1a;仿函数一、优先级队列#xff1a;1.引入2.介绍 二、priority_queue的模拟实现1.大体框架2.私有成员函数#xff1a;1.向下调整#xff08;AdjustDown#xff09;2.向上调整#xff08;AdjustUp#xff09; 3.公有成员函数1大小#xff08;… 文章目录 补充知识仿函数一、优先级队列1.引入2.介绍 二、priority_queue的模拟实现1.大体框架2.私有成员函数1.向下调整AdjustDown2.向上调整AdjustUp 3.公有成员函数1大小size.2是否为空empty.3.移除堆顶的元素pop4.元素插入push5.堆顶的元素top6.构造函数1.默认无参构造2.迭代器构造 补充知识仿函数 C仿函数function object是一种可以像函数一样调用的对象。仿函数通常是一个类它重载了函数调用运算符operator()使得对象可以被调用。 一、优先级队列
1.引入 优先级队列Priority Queue在底层实现上使用了一种称为堆Heap的数据结构通常使用数组比如C中的std::vector来表示。堆是一种完全二叉树数据结构具有以下特点 堆是一个完全二叉树也就是说除了最底层其他层都必须是完全填满的最底层的节点依次从左到右填充。 2.堆中的每个节点的值都大于等于或小于等于其子节点的值这就是所谓的堆序性质。 2.介绍 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 pop_back()删除容器尾部元素标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。 虽然底层实现中使用了vector但优先级队列仍然保持了队列的特性即根据优先级出队元素
二、priority_queue的模拟实现
1.大体框架
namespace simulation {
templateclass T, class Container vectorT, class Compare lessT//Compare这里传的是仿函数默认为系统里自带的less仿函数也可以自己添加//用于比较大小Container为底层实现容器默认为vectorclass priority_queue {private://私有成员函数void AdjustDown(int parent) { }void AdjustUp(int child) {}public://公有成员函数void pop() { }void push(const T x) {}const T top() { }bool empty() {}size_t size() {}priority_queue(){}private:Container _con;//成员变量};2.私有成员函数
1.向下调整AdjustDown 图中是在建小堆但我们代码以大堆为例除了大于小于的方向不同但逻辑是一样的
void AdjustDown(int parent) {//向下调整条件// 左右子树都是大堆/小堆int child parent * 2 1;Compare com;//仿函数的实例化while (child _con.size()) {if (child 1 _con.size() com(_con[child], _con[child 1])) {child;//选出两个孩子中最大的那一个}if (com(_con[parent], _con[child])) {//最大的那一个去与父母比较swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else {break;}}}2.向上调整AdjustUp void AdjustUp(int child) {//向上调整条件// 除了child这个位置前面的数据构成堆int parent (child - 1) / 2;Compare com;while (child 0) {if (com(_con[parent], _con[child])) {swap(_con[parent], _con[child]);child parent;//接着向上parent (child - 1) / 2;}else {break;}}}3.公有成员函数
1大小size.
2是否为空empty.
3.移除堆顶的元素pop void pop() {swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}4.元素插入push void push(const T x) {_con.push_back(x);//新元素向上调整AdjustUp(_con.size() - 1);}5.堆顶的元素top
const T top() {return _con[0];}6.构造函数
1.默认无参构造
priority_queue() {
//内容可以什么都不写因为初始化会去内置类型不用管自定义类型会去调用其
//默认构造函数这里会直接调用成员变量_con的默认构造
//当你写了迭代器构造后这个无参构造你必须要有因为当你写了一个构造函数
//以后编译器就不会自己再生成默认构造函数}2.迭代器构造
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);}}
