网站页面分析范文,西安网站制作开发公司哪家好,portfolio做网站,曲靖市网站建设优先队列#xff08;priority_queue#xff09; 优先队列是一种特殊的队列#xff0c;它同一般队列一样#xff0c;都支持先入先出的规则#xff0c;但不同于一般队列的是#xff0c;它对存储的数据有着自己独特的存储风格。
priority_queueintpa;pa.push(1);pa…优先队列priority_queue 优先队列是一种特殊的队列它同一般队列一样都支持先入先出的规则但不同于一般队列的是它对存储的数据有着自己独特的存储风格。
priority_queueintpa;pa.push(1);pa.push(2);pa.push(3);pa.push(4);pa.push(5);int n pa.size();for (int i 0;i n ;i){cout pa.top() ;pa.pop();}cout endl;return 0;
代码运行结果为 5, 4, 3, 2, 1由此可见我们发现优先队列中的数据按一定的规则排序 优先队列是一个模板类拥有三个模板参数 T为存储的数据类型Container为容器如listvector等决定了优先队列中数据的存储方式Compare为比较方法 它对存储的数据进行排序提供比较方法 优先队列的模板参数中除了第一个数据类型没有缺省值其他两个均有缺省值也代表在实际使用中我们不显示写出后两个模板参数也可以。
优先队列会对每一个存进的数据进行排序这类似于我们之前学习的一个数据结构也就是堆它会对新加入的数据元素进行向上调整也是排序堆有大堆和小堆同样优先队列也有。
priority_queueintq;//大堆
priority_queueint, vectorint, lessint q; // 大堆
priority_queueint, vectorint, greaterint q; // 小堆
less代表的是大堆greater代表的是小堆和我们日常的认知相违背我们记住就好c就是这么定义的less和greater是c中的两个比较函数 优先队列的接口 top取出队头元素pop删除队头元素push添加队元素并按照一定比较方法与前面的数据比较找到自己的新位置empty判断优先队列是否为空 优先队列的实现
namespace Yu
{templateclass Tclass Less//我要用这个仿函数建立大堆契合c父亲大于孩子{public:bool operator()(T x, T y){return x y;}};templateclass Tclass Great//用这个建立小堆父亲小于孩子{public:bool operator()(T x, T y){return x y;}};templateclass T,class continervectorT,class comprelessTclass priority_queue{public:void AdjustUp( size_t child){compre com;int parent (child - 1) / 2;while (child0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}void Adjust_Down( size_t parent){compre com;int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child],_con[child1])){child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}size_t size(){return _con.size();}void push(const T x){_con.push_back(x);AdjustUp(_con.size() - 1);}T top(){return _con[0];}void pop(){int end _con.size() - 1;swap(_con[0], _con[end]);_con.pop_back();Adjust_Down(0);}private:continer _con;};
} 由先前的介绍我们可以知道优先队列存储数据的形式类似于堆所以我们在实现优先队列的时候基本上就是手撕堆但也不是原搬堆。
首先我们因为需要存储多种类型的数据不可能仅仅针对某一个数据类型创建单独的数据结构去针对它所以我们一般用模板 templateclass T,class continervectorT,class comprelessT class priority_queue 如上所示贴合stl中的优先队列我们也给我们的优先队列三个模板参数第一个是我们存储的数据类型第二个是我们的容器第三个是比较方法用来切换大堆小堆模式 接口实现
1.push
void AdjustUp( size_t child){compre com;int parent (child - 1) / 2;while (child0){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(_con.size() - 1);} 当我们push进一个数据元素它就要与前面已经存储的数据元素进行排序找到自己的位置就和堆一样每进入一个新数据就要进行向上调整向上调整和向下调整前提都是建立在已经是堆的基础上但我们这里不需要考虑因为每次数据进入前之前的数据已经是堆了第一个数据默认是堆。
我们这里的向上调整函数只用传一个参数原因是我们的成员变量可以被成员函数随意访问并且我们的成员变量是容器它本身也可以调用一些函数来获取自身的大小。
2.pop
void Adjust_Down( size_t parent){compre com;int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child],_con[child1])){child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}else{break;}}}
void pop(){int end _con.size() - 1;swap(_con[0], _con[end]);_con.pop_back();Adjust_Down(0);} 删除数据同堆一样为了最求效率化将最末尾的数据和头部数据进行值交换如何在使堆的大小减一并采用向下调整的方式重新排列使其再次成为新的堆不过这次的头部数据是比之前的头部数据小或者大的第二数据向下调整的基础是本身是堆这里符合条件故可以用向下调整。
3top T top(){return _con[0];}
很简单的一段代码得益于容器本身的多功能性
4.empty
bool empty
{return ——con.empty();
} 仿函数的介绍 我们之前提到优先队列模板参数中需要传输比较方法但模板参数只能传输一个类型不能传递函数这里就需要用到仿函数 所谓的仿函数就是模拟函数它是利用模板类和重载符合运算符来实现的具体看代码 templateclass Tclass 类名{返回类型 operator()(参数列表){函数体; }};
这就是一个仿函数的基本书写形式用模板类是使其更加灵活能够处理更多的数据类型平常定义的时候我们需要根据想要的功能来书写函数体调用的时候直接创建一个类对象 类对象参数列表 这就是仿函数的调用形式。
仿函数的优越性在于简单与自定义你可以根据你的需求去书写函数体用他实现你的功能然后可以根据模板参数选择要处理的数据类型。
注意我们一般将类名与要实现的功能联系起来这样可以提高代码的可读性。
