文章目录priority_queue一.优先队列简介二.优先队列特性和操作1.头文件定义2.默认优先输出大数据1.举例3.优先输出小数据 即小顶堆1).举例4.自定义优先级 重载默认的 符号(1).使用 funtion .(2). 自定义数据类型三.基本函数实现1.构造函数2.添加函数3.删除函数4.判断函数5.大小函数6.其他函数7.总结代码详解1.基本类型优先队列的例子2.用pair做优先队列元素的例子3.用自定义类型做优先队列元素的例子priority_queue优先队列(priority_queue)实际上它的本质就是一个heap可以参考传送门这个写的也不错优先级队列是一个拥有权值观念的queue。它允许在底端添加元素、在顶端去除元素、删除元素。 缺省情况下优先级队列利用一个大顶堆完成。而CSTL中的优先队列就是在这个队列的基础上把其中的元素加以排序。其内部实现是一个二叉堆。所以优先队列其实就是把堆模板化将所有入队的元素排成具有单调性的一队方便我们调用。一.优先队列简介普通的队列是一种先进先出的数据结构元素在队列尾追加而从队列头删除。在优先队列中元素被赋予优先级。当访问元素时具有最高优先级的元素最先删除。优先队列具有最高级先出 first in, largestout的行为特征。首先要包含头文件#include, 他和queue不同的就在于我们可以自定义其中数据的优先级,让优先级高的排在队列前面,优先出队。二.优先队列特性和操作优先队列具有队列的所有特性包括队列的基本操作只是在这基础上添加了内部的一个排序它本质是一个堆实现的。1.头文件定义#includequeue#includefunctional//greater// 定义priority_queueintpq;2.默认优先输出大数据priority_queueType, Container, Functional其中,Type为数据类型.Container为保存数据的容器.Functional为元素比较的方式.若不写后面两个参数.容器 默认使用vector比较方式 默认使用operator 即优先队列是大顶堆. 队头元素最大大根堆声明方式大根堆就是把大的元素放在堆顶的堆。优先队列默认实现的就是大根堆所以大根堆的声明不需要任何花花肠子直接按CSTL的声明规则声明即可。#includequeuepriority_queueintq;priority_queuestringq;priority_queuepairint,intq;C中的int,string等类型可以直接比较大小所以不用我们多操心优先队列自然会帮我们实现。但是如果是我们自己定义的结构体就需要进行重载运算符了1.举例srand(time(NULL));priority_queueintpq1;// 默认是最大堆...std::coutstart...endl;for(inti0;i10;i){inttrand()%100;couttends;pq1.push(t);}std::coutendl;while(!pq1.empty()){coutpq1.top()ends;pq1.pop();}coutendl;输出3.优先输出小数据 即小顶堆priority_queueint, vectorint, greaterint p;使用greaterint. 即改用operator 小根堆声明方式大根堆是把大的元素放堆顶小根堆就是把小的元素放到堆顶。实现小根堆有两种方式第一种是比较巧妙的因为优先队列默认实现的是大根堆所以我们可以把元素取反放进去因为负数的绝对值越小越大那么绝对值较小的元素就会被放在前面我们在取出的时候再取个反就瞒天过海地用大根堆实现了小根堆。第二种小根堆有自己的声明方式我们记住即可我也说不明白道理priority_queueint,vectorint,greaterintq;注意当我们声明的时候碰到两个“或者”放在一起的时候一定要记得在中间加一个空格。这样编译器才不会把两个连在一起的符号判断成位运算的左移/右移。1).举例priority_queueint,vectorint,greaterintpq2;// 最小堆std::coutstart...endl;for(inti0;i10;i){inttrand()%100;std::couttends;pq2.push(t);}std::coutendl;while(!pq2.empty()){coutpq2.top()ends;pq2.pop();}coutendl;结果4.自定义优先级 重载默认的 符号(1).使用 funtion .// 定义比较函数// 后面一个表示栈顶元素? 所以这个是 最小堆boolmyCom(inta,intb){returna%10b%10;}// 使用priority_queueint,vectorint,functionbool(int,int)pq3(myCom);std::coutstart...endl;for(inti0;i10;i){inttrand()%100;std::couttends;pq3.push(t);}std::coutendl;while(!pq3.empty()){coutpq3.top()ends;pq3.pop();}coutendl;输出结果(2). 自定义数据类型#includeiostream#includequeue#includecstdlibusingnamespacestd;structNode{intx,y;Node(inta0,intb0):x(a),y(b){}};structcmp{booloperator()(Node a,Node b){if(a.xb.x)returna.yb.y;returna.xb.x;}};intmain(){priority_queueNode,vectorNode,cmpp;for(inti0;i10;i)p.push(Node(rand(),rand()));while(!p.empty()){coutp.top().x p.top().yendl;p.pop();}//while//getchar();return0;三.基本函数实现首先函数在头文件中归属于命名空间std使用的时候需要注意。priority_queueintq1;priority_queuepairint,intq2;// 注意在两个尖括号之间 一定要留空格。priority_queueint,vectorint,greaterintq3;// 定义小的先出队1.构造函数1.普通方法priority_queueintq;//通过操作按照元素从大到小的顺序出队priority_queueint,vectorint,greaterintq;//通过操作按照元素从小到大的顺序出队2、自定义优先级structcmp{booloperator()(intx,inty){returnxy;// x小的优先级高//也可以写成其他方式//如 return p[x] p[y];表示p[i]小的优先级高}};priority_queueint, vector, cmp q; //定义方法//其中第二个参数为容器类型。第三个参数为比较函数。3、结构体声明方式structnode{intx,y;friendbooloperator(node a,node b){returna.xb.x;//结构体中x小的优先级高}};priority_queuenodeq;//定义方法//在该结构中y为值, x为优先级。//通过自定义operator操作符来比较元素中的优先级。//在重载””时最好不要重载””可能会发生编译错误2.添加函数q.push();插入元素到队尾 (并排序)q.emplace(); 原地构造一个元素并插入队列3.删除函数q.pop();弹出队头元素4.判断函数q.empty();队列是否为空5.大小函数q.size()返回队列内元素个数6.其他函数q.top();访问队头元素,返回队列首元素不改变队列swap交换内容7.总结top 访问队头元素empty 队列是否为空size 返回队列内元素个数push 插入元素到队尾 (并排序)emplace 原地构造一个元素并插入队列pop 弹出队头元素swap 交换内容用法作用q.top()返回priority_queue的首元素q.push()向priority_queue中加入一个元素q.size()返回priority_queue当前的长度大小q.pop()从priority_queue队头删除一个元素q.empty()返回priority_queue是否为空1为空、0不为空注意priority_queue取出队首元素是使用top而不是front这点一定要注意代码详解1.基本类型优先队列的例子#includeiostream#includequeueusingnamespacestd;intmain(){//对于基础类型 默认是大顶堆priority_queueinta;//等同于 priority_queueint, vectorint, lessint a;// 这里一定要有空格不然成了右移运算符↓↓priority_queueint,vectorint,greaterintc;//这样就是小顶堆priority_queuestringb;for(inti0;i5;i){a.push(i);c.push(i);}while(!a.empty()){couta.top() ;a.pop();}coutendl;while(!c.empty()){coutc.top() ;c.pop();}coutendl;b.push(abc);b.push(abcd);b.push(cbd);while(!b.empty()){coutb.top() ;b.pop();}coutendl;return0;}运行结果4 3 2 1 00 1 2 3 4cbd abcd abc请按任意键继续. . .2.用pair做优先队列元素的例子规则pair的比较先比较第一个元素第一个相等比较第二个。#includeiostream#includequeue#includevectorusingnamespacestd;intmain(){priority_queuepairint,inta;pairint,intb(1,2);pairint,intc(1,3);pairint,intd(2,5);a.push(d);a.push(c);a.push(b);while(!a.empty()){couta.top().first a.top().second\n;a.pop();}}运行结果2 51 31 2请按任意键继续. . .3.用自定义类型做优先队列元素的例子#includeiostream#includequeueusingnamespacestd;//方法1structtmp1//运算符重载{intx;tmp1(inta){xa;}booloperator(consttmp1a)const{returnxa.x;//大顶堆}};//方法2structtmp2//重写仿函数{booloperator()(tmp1 a,tmp1 b){returna.xb.x;//大顶堆}};intmain(){tmp1a(1);tmp1b(2);tmp1c(3);priority_queuetmp1d;d.push(b);d.push(c);d.push(a);while(!d.empty()){coutd.top().x\n;d.pop();}coutendl;priority_queuetmp1,vectortmp1,tmp2f;f.push(b);f.push(c);f.push(a);while(!f.empty()){coutf.top().x\n;f.pop();}}运行结果321321请按任意键继续. . .