深圳网站制作公司哪家好,网站备案主体负责人,北京网站建设网,想弄个网站✨✨小新课堂开课了#xff0c;欢迎欢迎~✨✨ #x1f388;#x1f388;养成好习惯#xff0c;先赞后看哦~#x1f388;#x1f388; 所属专栏#xff1a;C#xff1a;由浅入深篇 小新的主页#xff1a;编程版小新-CSDN博客 一.priority_queue的介绍
优先级队列被实现… ✨✨小新课堂开课了欢迎欢迎~✨✨ 养成好习惯先赞后看哦~ 所属专栏C由浅入深篇 小新的主页编程版小新-CSDN博客 一.priority_queue的介绍
优先级队列被实现为容器适配器容器适配器就是将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部并且它的第一个元素总是它所包含的元素中最大的。因为默认情况下priority_queue是大堆。
底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器支持随机访问迭代器访问以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。
二.priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。 注意默认情况下priority_queue是大堆。 2.1priority_queue的定义 1.指定定义 //指定定义
//1.以vector作为底部容器类内部构建大堆结构
priority_queueint, vectorint, lessint pq1;//2.以vector作为底部容器类内部构建小堆结构
priority_queueint, vectorint, greaterint pq2; 2.未指定定义 //未指定定义
priority_queueint pq3;//默认以vector作为底层容器类内部构建大堆结构 2.2priority_queue的常见操作
函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否则返回falsetop( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
void priority_queue1()
{priority_queueint pq1;pq1.push(3);pq1.push(7);pq1.push(2);pq1.push(5);pq1.push(8);pq1.push(1);pq1.push(6);pq1.push(4);//插入while (!pq1.empty()){cout pq1.top() ;//返回堆顶元素pq1.pop();//删除堆顶元素}//8 7 6 5 4 3 2 1
}三.priority_queue的模拟实现
我们在模拟实现priority_queque之前要先复习一下两个堆算法这里我们就以构建大堆结构为例。
3.1向上调整建堆
以大堆为例向上调整建堆就是在堆的末尾插入一个数据后经过向上调整依然是一个大堆。 调整思想 1、将目标结点与其父结点进行比较。 2、若目标结点的值比其父结点的值大则交换目标结点与其父结点的位置并将原目标结点的父结点当作新的目标结点继续进行向上调整直到目标节点的值比其父节点的值小位置位置调整完毕。 3.2向下调整建堆
以大堆为例向下调整算法是为了删除堆顶数据在删除堆顶数据后让该堆依旧是大根堆。 调整思想 1、将目标结点与其较大的子结点进行比较。 2、若目标结点的值比其较大的子结点的值小则交换目标结点与其较大的子结点的位置并将原目标结点的较大子结点当作新的目标结点继续进行向下调整直到目标节点比其较大的子节点的值大为止调整完成。 3.3priority_queue的模拟实现
函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty( )检测优先级队列是否为空是返回true否则返回falsetop( )返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
namespace fu
{//内部构建大根堆template class Tstruct less{bool opeartor()(const T x, const T y){return x y;}};//内部构建小跟堆template class Tstruct greater{bool opeartor()(const T x, const T y){return x y;}};//优先级队列模拟实现templateclass T, class Container vectorint, class Compare lessTclass priority_queue{public://向上调整建堆void AdjustUp(int child){int parent (child - 1) / 2;while (child 0){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}//插入数据void push(const T x){_con.push_back(x);AdjustUp(x);}//向下调整建堆void AdjustDown(int n, int parent){int child 2 * parent 1;while (child n){if (child 1 n _comp(_con[child], _con[child 1])){child;}if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child 2 * parent 1;}else{break;}}}//删除数据void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(_con.size(),0);}//访问堆顶元素T top(){return _con[0];}const T top() {return _con[0];}//返回有效元素个数size_t size() {return _con.size();}//判断队列是否为空bool empty() {return _con.empty();}private:Container _con;Compare _com;};
}感谢各位大佬的观看创作不易还请各位大佬支持~
