甘肃省建设厅注册中心网站,梧州网站设计制作服务至上,名费网站制作视频教程,wordpress加导航菜单目录 一.priority_queue的使用
1.1、基本介绍
1.2、优先级队列的定义
1.3、基本操作(常见接口的使用#xff09;
1.4、重写仿函数支持自定义数据类型
二.priority_queue的模拟实现
2.1、构造重要的调整算法
2.2、常见接口的实现
push()
pop()
top()
empt…目录 一.priority_queue的使用
1.1、基本介绍
1.2、优先级队列的定义
1.3、基本操作(常见接口的使用
1.4、重写仿函数支持自定义数据类型
二.priority_queue的模拟实现
2.1、构造重要的调整算法
2.2、常见接口的实现
push()
pop()
top()
empty()、size() 三.利用仿函数改进调整算法 一.priority_queue的使用
1.1、基本介绍
我们之前讲过数据结构中的队列它具有先进先出的特性FIFO.添加元素时只能在队尾插入删除元素时只能删除队首的元素.
而优先级队列它并不满足先进先出的特性倒像是数据结构中的“堆”. 优先级队列每次出队时只能是队列中优先级最高的元素而不是队首的元素。
这个优先级可以通过元素的大小或者赋值运算符重载等进行比较. 例如定义元素越大优先级越高那么每次出队的时候一定是队列中最大的元素因为它的优先级最高.并且重新进行维护.
经过上述的说明是不是和我们所说的“堆”很相似优先级队列的内部确实是由堆结构实现.
下面是官方文档的一段介绍 1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。 1.2、优先级队列的定义
首先使用优先级队列需要包含头文件queue,priority_queue的定义如下 template class T, class Container vectorT, class Compare lesstypename Container::value_type class priority_queue;第一个模板参数为为class T代表每个元素的类型. 第二个模板参数为class Container缺省值为vectorT,代表存储这些数据的容器可以是vectordeque等但不能是list因为它的内部空间不连续. 第三个模板参数为class Compare缺省值为lessT,其中less是个仿函数是降序排序既优先级最大的是容器中最大的元素.又叫比较函数. 当然可以升序排序把less改为greater即可. less 和 greater使用的前提是建立在这些数据类型是C基本的数据类型. 例如下面这段代码 //不写后面两个参数默认为vectorlesspriority_queueint pq1;//建立一个优先级队列(大堆)数据类型是int利用vector容器实现less降序实现priority_queueint, vectorint, lessint pq2;//建立一个优先级队列(小堆)数据类型是int利用vector容器实现greater降序实现priority_queueint, vectorint, greaterint pq3;
1.3、基本操作(常见接口的使用
它的操作与基本队列操作一样主要有以下接口
top() 返回元素中第一个元素的引用优先级最高的元素都会被放到顶部既第一个元素.
push()插入一个元素并重新维护堆无返回值.
pop() 删除优先级最高的元素并重新维护堆无返回值
size() 返回容器中有效元素的数量返回队列的大小
empty() 检测容器是否为空.返回“true”或者“false”.
代码示例
int main()
{//不写后面两个参数默认为vectorlesspriority_queueint pq1;//push的使用pq1.push(1);pq1.push(2);pq1.push(3);pq1.push(4);pq1.push(5);//push完之后维护也完毕此时优先级最高的是元素是5排在第一位cout pq1.top() endl;//优先级最高的一位所以应该是5//pop的使用删除一个优先级最高的元素5此时重新调整优先级最高的元素应该为4pq1.pop();cout pq1.top() endl;//size()的使用,删除了一个元素此时应该还有四个元素cout pq1.size() endl;return 0;
}
执行结果 正如我们预料所得.
1.4、重写仿函数支持自定义数据类型
仿函数是通过重载‘()’运算符来进行模拟函数操作的类. 通俗点说,仿函数是一个能行使函数功能类,然后类里必须实现“()”运算符重载.
比如我们要根据类里的某一个成员大小进行比较因为是一个类它不是C里的基本数据类型所以需要我们自己重新仿函数来支持它.
看下面这段程序
class Data
{
public:Data(int i, int d):id(d), data(d){}int GetData() const{return data;}
private:int id;int data;
};
//仿函数从小到大排序既大的优先级最高
class cmp
{
public:bool operator() (Data d1, Data d2){return d1.GetData() d2.GetData();}
};
int main()
{//首先创建三个data类型数据Data* d1 new Data(0, 1);Data* d2 new Data(0, 2);Data* d3 new Data(0, 3);//创建优先级队列比较函数为cmp仿函数并将数据全部pushpriority_queueData,vectorData,cmp pq;pq.push(*d1);pq.push(*d2);pq.push(*d3);//全部输出出来while(!pq.empty()){cout (pq.top().GetData()) endl;pq.pop();}return 0;
}
二.priority_queue的模拟实现
2.1、构造重要的调整算法
priority_queue的底层结构就是堆所以模拟实现只需要对堆封装即可.
所以其中大部分都是与之前堆的数据结构相关的一些方法.
我们知道priority_queue有三个参数来构造所以我们也使用三个模板参数.
模板如下 templateclass T,class Container vectorT,class Compare lessT然后一个类须有成员变量这个类里只有一个成员变量 Container _con;
利用第二个模板参数既容器类型的构造了一个变量这样就可以对里面的所有数据进行操作了.
准备就绪后开始写构造函数主要有两种无参构造以及迭代器构造.
无参构造其实可以不用写但是由于有迭代器构造函数的存在系统便不能再调用默认构造函数,所以必须自己手写一下无参的构造函数. priority_queue(){}
迭代器构造
和之前的迭代器构造方法一样看一下便知. 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--)//[_con.size()-1]是最后一个元素的下标再-1然后/2是计算中间的元素既最后一个结点的父节点{adjust_down(i);} 既从数据中间的一个元素开始每次进行向下调整算法完毕之后--指向下一个数据继续进行调整如此直到第一个元素建堆便完成.
提到了向下调整算法这个方法在我之前堆的文章中有详细介绍过大家可以去看之前的文章进行理解.
. void adjust_down(size_t parent){size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child] _con[child 1])child;if (_con[child] _con[parent]){swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}elsebreak;}}
大概总固体思路是先根据根节点找到孩子结点然后判断左右两个孩子结点中的哪个大默认是孩子结点是左孩子结点如果右孩子结点比左孩子结点大那么直接即可就是右孩子结点.
然后再判断如果孩子结点的值大于父节点的值则交换并且更新父节点和孩子结点的值. 与此对应的是既然有向下调整算法那么也会有向上调整算法.
前面的文章也有写到过不再详述. void adjust_up(size_t child){size_t parent (child - 1) / 2;while (child 0){if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}}
这个是传入孩子结点我们根据公式求出父亲结点公式就是代码中所写的那一个.
然后判断符合条件更新父节点和子结点即可.
两大基础调整算法写完那后面的就非常轻松了
2.2、常见接口的实现
这些接口都可以复用之前的调整算法.
push()
这个就是将数据插入并且重新调整堆的结构. void push(const T x){_con.push_back(x);adjust_up(_con.size()-1);//传入最后一个数据的下标}
对于push_back()有人可能有疑问包括我就是我没有实现push_back()但为什么可以直接写呢
其实我们能用优先级队列的容器就那么几种vectordeque等等都是一些内部存储空间连续的而这些容器都具有push_back()这个接口所以到时候模板实例化的时候便可以用了.
pop()
先把首尾元素进行交换然后删除最后一个元素再进行向下调整. void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}
top()
返回优先级最高既堆顶的元素既容器的首元素.由于堆顶特性堆中 const T top(){return _con[0];}
empty()、size()
这些都是容器中所对应拥有的函数直接返回即可. bool empty() const{return _con.empty();}size_t size() const{return _con.size();} 三.利用仿函数改进调整算法
通过我们上面写的向上调整向下调整算法发现有一个比较麻烦的地方
就是它其中的每次比较都是大于既每次都是大顶堆
但是如果我们想要小顶堆怎么办只能一点一点的改大小于符号 很容易就会混和忘记非常的不方便.
这个时候我们便可以使用仿函数来解决这个问题.这个时候便用到刚开始写的三个模板参数中的第三个参数了.
可以先写两个仿函数一个用来构造小顶堆另外的是大顶堆.
templateclass Tclass less{public:bool operator()(const T l, const T r){return l r;}};templateclass Tclass greater{public:bool operator()(const T l, const T r){return l r;}}; 我们再把它应用到那两个调整算法里面.
adjust_up
最开始需要用仿函数构造一个对象才可以使用. Compare com;
原来其中的 if (_con[child] _con[parent])
改为 if (com(_con[child] , _con[parent]))
adjust_down
最开始需要用仿函数构造一个对象才可以使用. Compare com;
原来其中的 if (child 1 _con.size() _con[child] _con[child 1]) if (_con[child] _con[parent])
改为 if (child 1 _con.size() com(_con[child] , _con[child 1])) if (com(_con[child] , _con[parent]))
这样就改进完成了.以后想要改变大小顶堆时只需要将Compare后面的仿函数改成自己需要的即可.
这就是优先级队列的所有内容了包括使用及实现.
由于文章代码比较散乱这里直接放上总代码方便参观.
#pragma once
#includeiostream
#includevectorusing namespace std;
namespace hyx
{//大堆templateclass T,class Container vectorT,class Compare lessTclass priority_queue{templateclass Tclass less{public:bool operator()(const T l, const T r){return l r;}};templateclass Tclass greater{public:bool operator()(const T l, const T r){return l r;}};public:priority_queue(){}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--){adjust_down(i);}}void adjust_up(size_t child){Compare com;size_t parent (child - 1) / 2;while (child 0){if (com(_con[child] , _con[parent])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}}void adjust_down(size_t parent){Compare com;size_t child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child] , _con[child 1]))child;if (com(_con[child] , _con[parent])){swap(_con[child], _con[parent]);parent child;child 2 * parent 1;}elsebreak;}}void push(const T x){_con.push_back(x);adjust_up(_con.size()-1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con[0];}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}private:Container _con; };}
