一般网站用什么数据库,游戏源码搭建,英文网站建设口碑好,镇江百度送网站文章目录 priority_queuepriority_queue 使用priority_queue的模拟实现向上调整算法向下调整算法pushpoptopsizeempty 仿函数完整代码 priority_queue
优先队列#xff08;priority_queue#xff09;也是队列的一种#xff0c;priority_queue的接口是和queue的接口是相同的… 文章目录 priority_queuepriority_queue 使用priority_queue的模拟实现向上调整算法向下调整算法pushpoptopsizeempty 仿函数完整代码 priority_queue
优先队列priority_queue也是队列的一种priority_queue的接口是和queue的接口是相同的。所以两者的使用语法也是相同的。我们直接看优先队列priority——queue的底层实现原理。
默认情况下priority_queue是大堆。
priority_queue 使用
//用vector作为底层容器内部构造大堆结构。
priority_queueint, vectorint, lessint q1;
//用vector作为底层容器内部构造小堆结构。
priority_queueint, vectorint, greaterint q2;
//不指定底层容器和内部需要构造的堆结构。
priority_queueint q3;#include iostream
#include functional
#include queue
using namespace std;
int main()
{priority_queueint q;q.push(3);q.push(6);q.push(0);q.push(2);q.push(9);q.push(8);q.push(1);while (!q.empty()){cout q.top() ;q.pop();}cout endl; //9 8 6 3 2 1 0return 0;
}
priority_queue的模拟实现
priority_queue的底层实际上就是堆模拟实现priority_queue之前需要知道向下调整和向上调整算法。下面这两种算法我们均以大堆为例
向上调整算法
向上调整算法的前提 若想将其调整为小堆那么根结点的左右子树必须都为小堆。 若想将其调整为大堆那么根结点的左右子树必须都为大堆
向堆中插入数据需要使用到向上调整算法 先将元素插入到堆的末尾,即最后一个孩子之后从插入节点位置开始和父节点比较我们以大堆为例如果目标结点的值比父结点的值大则交换目标结点与其父结点的位置并将原目标节点的父节点当作新的目标节点继续向上调整调整到根节点结束此时该树已经是大堆了
图中是以小堆为例
向下调整算法
向下调整算法的前提 若想将其调整为小堆那么根结点的左右子树必须都为小堆。 若想将其调整为大堆那么根结点的左右子树必须都为大堆 从根节点开始选出左右孩子值较大的节点让值较大的节点与父节点的值进行比较如果值较大的节点比父节点的值小交换两者位置将原来值较大的孩子节点作为父节点继续向下调整调整到叶子节点结束
图中是以小堆为例
push void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);}pop void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}top
const T top(){return _con[0];}size
bool size(){return _con.size();} empty
bool empty(){return _con.empty();}仿函数
using namespace std;
//仿函数 /函数对象
template class T
class Less
{
public:bool operator() (const T x, const T y){return x y;}
};int main()
{Lessint lessfunc;bool result lessfunc(6, 2);//仿函数//bool result lessfunc.operator()(6, 2);cout boolalpha result endl;return 0;
}完整代码
#pragma once
#includevector
#includefunctional
using namespace std;//仿函数 /函数对象
template class T
class Less
{
public:bool operator() (const T x, const T y){return x y;}
};
template class T
class Greater
{
public:bool operator() (const T x, const T y){return x y;}
};namespace cxq
{templateclass T, class Container vectorT, class Compare LessT class priority_queue{private:void AdjustDown(int parent)//从根节点开始{Compare com;//仿函数int child parent * 2 1;while (child _con.size()){//假设默认左孩子大于右孩子// if (child 1 _con.size() _con[child 1] _con[child])//右孩子要存在防止越界if (child 1 _con.size() com(_con[child 1], _con[child])){child;}//if (_con[child] _con[parent])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);int parent child;child parent * 2 1;}else{break;}}}void AdjustUp(int child){Compare com;//仿函数int parent (child - 1) / 2;//大堆while (child 0){//if (_con[child] _con[parent])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);int child parent;parent (child - 1) / 2;}else{break;}}}public://默认构造priority_queue(){}templateclass InputIterator//构造函数priority_queue(InputIterator first, InputIterator last){while (first ! last){_con.push_back(*first);first;}//建堆//最后一个非叶子节点for (size_t 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();}bool size(){return _con.size();}private:Container _con;};void test_priority_queue1(){//默认是大堆--less//priority_queueint pq;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;}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);//声明private:int _year;int _month;int _day;};ostream operator(ostream _cout, const Date d){_cout d._year - d._month - d._day;return _cout;}struct LessPDate{//仿函数bool operator() ( const Date * p1 , const Date* p2){return *p1 *p2;}};void test_priority_queue2(){//priority_queueDate pq;//pq.push(Date(2023, 7, 20));//pq.push(Date(2023, 6, 20));//pq.push(Date(2023, 8, 20));//while (!pq.empty())//{// cout pq.top() ;// pq.pop();//}//cout endl;priority_queueDate*, vectorDate*, LessPDate pq;pq.push(new Date(2023, 7, 20));pq.push(new Date(2023, 6, 20));pq.push(new Date(2023, 8, 20));while (!pq.empty()){cout *pq.top() ;pq.pop();}cout endl;}}
