什么建站程序好收录,江苏建设行业证书编号查询网站,河北做网站的公司,合浦网站建设目录 前言 一、priority_queue的使用 1. 成员函数 2. 例题 二、仿函数 三、模拟实现 1. 迭代器区间构造函数 AdjustDown 2. pop 3. push AdjustUp 4. top 5. size 6. empty 四、完整实现 总结 前言 优先级队列以及前面的双端队列基本上已经脱离了队列定… 目录 前言 一、priority_queue的使用 1. 成员函数 2. 例题 二、仿函数 三、模拟实现 1. 迭代器区间构造函数 AdjustDown 2. pop 3. push AdjustUp 4. top 5. size 6. empty 四、完整实现 总结 前言 优先级队列以及前面的双端队列基本上已经脱离了队列定义只是占了队列名字 优先级队列——priority_queue 1. 优先级队列是一种容器适配器根据一些严格的弱排序标准经过专门设计其第一个元素始终是它所包含的最大元素。 2. 此上下文类似于堆其中元素可以随时插入并且只能检索最大堆元素优先级队列中顶部的元素。 3. 优先级队列作为容器适配器实现容器适配器是使用特定容器类的封装对象作为其基础容器的类提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”弹出这称为优先级队列的顶部。 4. 底层容器可以是任何标准容器类模板也可以是一些其他专门设计的容器类。容器应可通过随机访问迭代器访问并支持以下操作 emptysizefrontpush_backpop_back 5. 标准容器类vector和deque满足这些要求。默认情况下如果未为特定priority_queue类实例化指定容器类则使用标准容器vector。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。这是由容器适配器通过自动调用算法函数 make_heap、push_heap、pop_heap 自动完成的并在需要时完成。 注意 priority_queue还是适配器但是适配的是vector底层是二叉树的堆priority_queue仍然包括在queue头文件中 默认大堆Compare的缺省是less表示的是大根堆 可以使用仿函数修改为小根堆 priority_queueint, dequeint, greaterint pq; 一、priority_queue的使用
1. 成员函数 2. 例题
215. 数组中的第K个最大元素 方法一直接使用sort排序 class Solution {
public:int findKthLargest(vectorint nums, int k) {sort(nums.begin(), nums.end(), greaterint());return nums[k - 1];}
}; 方法二优先级队列建大堆 class Solution {
public:int findKthLargest(vectorint nums, int k) {priority_queueint pq(nums.begin(), nums.end());while (--k){pq.pop();}return pq.top();}
}; 方法三维护一个有K个数据的小堆遍历nums数组若比top()值大就入堆最后返回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();}
}; 注意 sort函数最后一个参数是greaterint()是一个匿名对象而在priority_queue内部第三个模板是greaterint是类型不能加括号 二、仿函数 我们在之前就遇到过sort函数如果想实现降序需要加上仿函数greater类型()那么什么是仿函数呢它又有什么作用
我们来看一个简单的例子
class Fun
{
public:bool operator()(int a, int b){return a b;}
};int main()
{ Fun func;cout func(1, 2) endl;//等价于cout func.operator()(1, 2) endl;return 0;
} 这里的Fun就是仿函数由Fun类定义的对象称为函数对象仿函数顾名思义一个类的对象可以像函数一样使用它替代了c语言里的函数指针我们只需要重载 () 符号就可以像使用函数一样调用它的 () 运算符重载函数 那么这样的仿函数有什么作用呢 替代c语言的函数指针因为c语言的函数指针很复杂、容易出错搭配模板可以实现多类型的函数运算不会将函数“写死”例如我们写Less、Greater类重载符号在需要的地方实例化函数对象如果有比较大小的情况就使用函数对象参数1参数2原理就是调用operator()函数像函数一样调用 下面是priority_queue带上第三个模板参数Less后使用仿函数的代码 templateclass T
class Less
{
public:bool operator()(const T a, const T b){return a b;}
};templateclass T
class Greater
{
public:bool operator()(const T a, const T b){return a b;}
};namespace my_priority_queue
{// LessT 才是Less类的类型templateclass T, class Container vectorT, class Compare LessTclass priority_queue{private://大堆向下调整void AdjustDown(int parent){//创建函数对象Less模板类型就是比较Greater模板类型就是比较Compare com;//找左右孩子中最大的哪一个int child parent * 2 1;while (child _con.size()){//因为com是比较小于关系所以需要将原先大于的表达式逆一下//判断右孩子是否存在/*if (child 1 _con.size() _con[child 1] _con[child])*/if (child 1 _con.size() com(_con[child], _con[child 1])){child;}//if (_con[child] _con[parent])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void AdjustUp(int child){Compare com;int parent (child - 1) / 2;while (child 0) //最坏情况孩子等于0时结束{if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent child - 1 1;}else{break;}}}public:templateclass InputIterator //input只写迭代器//迭代器区间构造函数priority_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);}private://容器Container _con;};
} 如果比较的类型是其他自定义类型并且该类没有重载operator函数那么我们就需要手写一个仿函数进行比较否则编译错误无法进行比较 因为库里的仿函数使用了模板是什么类型就按什么类型相比那么如果是new返回的指针类型由于每次new返回的地址相当于是随机的又比较的是指针类型的大小所以比较结果也是随机结果。所以我们还是需要写仿函数修改比较方式去比较指针指向的内容即可。 三、模拟实现 编译错误找不到出错位置怎么办 如果代码编译错误找不到在哪那么逐步屏蔽掉一些代码逐步排查是十分有效的找到错误处方法 priority_queue也同queue、stack一样是适配器适配vector容器
1. 迭代器区间构造函数 AdjustDown 采用封装容器vector的push_back尾插数据因为默认是大堆向下建堆所以尾插数据后将从最后一个元素的父亲结点—— (_con.size() - 1 - 1) / 2 开始向下调整。向下调整函数不用多说在二叉树部分我们详细讲解过 namespace my_priority_queue
{// LessT 才是Less类的类型templateclass T, class Container vectorT, class Compare LessTclass priority_queue{private://大堆向下调整void AdjustDown(int parent){//创建函数对象Less模板类型就是比较Greater模板类型就是比较Compare com;//找左右孩子中最大的哪一个int child parent * 2 1;while (child _con.size()){//因为com是比较小于关系所以需要将原先大于的表达式逆一下//判断右孩子是否存在/*if (child 1 _con.size() _con[child 1] _con[child])*/if (child 1 _con.size() com(_con[child], _con[child 1])){child;}//if (_con[child] _con[parent])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}public:templateclass InputIterator //input只写迭代器//迭代器区间构造函数priority_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);}}private://容器Container _con;};
} 2. pop 堆的pop将堆顶数据与最后一个数据进行交换再进行pop_back再将堆顶数据向下调整 void pop(){//交换后尾删并向下调整swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);} 3. push AdjustUp 尾插数据后将该数据向上调整 void AdjustUp(int child){Compare com;int parent (child - 1) / 2;while (child 0) //最坏情况孩子等于0时结束{if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent child - 1 1;}else{break;}}}void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);} 4. top 返回堆顶数据返回值是 const T const T top(){return _con[0];} 5. size 返回vector的size()即可 size_t size(){return _con.size();} 6. empty 直接调用vector的empty函数即可 size_t size(){return _con.size();} 四、完整实现
#pragma once
#includeiostream
#includevector
#includefunctional
using namespace std;templateclass T
class Less
{
public:bool operator()(const T a, const T b){return a b;}
};templateclass T
class Greater
{
public:bool operator()(const T a, const T b){return a b;}
};namespace my_priority_queue
{// LessT 才是Less类的类型templateclass T, class Container vectorT, class Compare LessTclass priority_queue{private://大堆向下调整void AdjustDown(int parent){//创建函数对象Less模板类型就是比较Greater模板类型就是比较Compare com;//找左右孩子中最大的哪一个int child parent * 2 1;while (child _con.size()){//因为com是比较小于关系所以需要将原先大于的表达式逆一下//判断右孩子是否存在/*if (child 1 _con.size() _con[child 1] _con[child])*/if (child 1 _con.size() com(_con[child], _con[child 1])){child;}//if (_con[child] _con[parent])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}void AdjustUp(int child){Compare com;int parent (child - 1) / 2;while (child 0) //最坏情况孩子等于0时结束{if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent child - 1 1;}else{break;}}}public:priority_queue(){}//迭代器区间构造函数templateclass InputIterator //input只写迭代器priority_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];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private://容器Container _con;};
}void test_priority_queue1()
{// 默认是大堆 -- less//priority_queueint pq;// 仿函数控制实现小堆my_priority_queue::priority_queueint, vectorint, Greaterint pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;
} 总结 priority_queue优先级队列就是存储在vector内的堆掌握向上向下调整函数可以回顾之前的文章堆的实现一节。 最后如果小帅的本文哪里有错误还请大家指出请在评论区留言ps抱大佬的腿新手创作实属不易如果满意还请给个免费的赞三连也不是不可以流口水幻想嘿那我们下期再见喽拜拜
