锐客网

  1. 首页 > 睿知 > it技术 > >

ACM学习|c++ STL 优先队列

acm竞赛ACM学习数据结构

前言：建议初学者跟着把每一个样例打一遍，并自己改变代码做到更多不同的效果。
优先队列是什么，干嘛用的 优先队列，即带有优先级的队列。不懂啥是队列的可以先去学队列了（先进先出的就是队列）。那么带有优先级，就是可以做到排序的队列，比如我依次放入2，1，3，小顶堆优先队列就可以通过1，2，3的顺序把他们吐出来。而一般的队列只能以2，1，3的顺序把他们吐出来。
作用：以最短路和BFS为例，就经常使用优先队列。当然其他问题和算法也经常使用优先队列。
要学些什么 学习优先队列的基础用法前，你可以啥也没学，只会用法就行。但是要想知道优先队列的原理，实现优先队列的自定义，建议至少把二叉树，堆排序给学了，最好把C++的类也学了。这里不会讲优先队列的原理，而是注重使用方法。这东西学会怎么用比学会原理的时间要早太多了。
【ACM学习|c++ STL 优先队列】如果代码看着眼花，那就跟着打一次，边打边尝试理解它的意思。
一定要上手实践
优先队列的定义：
priority_queue
Type 是数据类型；Container 是容器类型，一般使用vector；Functional 是比较的方式。
优先队列的基本操作：
  • top 访问队头元素
  • empty 队列是否为空
  • size 返回队列内元素个数
  • push 插入元素到队尾并排序
  • emplace 原地构造一个元素并插入队列
  • pop 弹出队头元素
  • swap 交换内容
基础使用
学会使用这部分前你不需要懂它到底啥原理。
注：
大顶堆：字面意思，根（顶）最大的堆。
小顶堆：根（顶）最小的堆。

#include #include #include #include using namespace std; //_________________默认为大顶堆_________________ priority_queue q1; //_________________标准一般写法_________________ //小顶堆 priority_queue,greater > q2; //大顶堆 priority_queue,less >q3; priority_queue, greater >q4; int main() { //测试样例1,默认情况 q1.push(2); q1.push(1); q1.push(4); cout<<"q1:"; while(!q1.empty()){ cout<


进阶使用
在学习这部分前，你可以不学前置知识，但顶多只能照猫画虎，建议现学上面提到的前置知识，再来学就很好懂了。
进阶1：pair
#include #include #include #include using namespace std; //_____________piar_________________ //标准写法 priority_queue,vector >,greater > >q1; //当然也可以简写，不过默认大顶堆 priority_queue >q2; int main() { //测试样例1: pair a(1,"issey"); pair b(1,"aaa"); pair c(2,"zz"); q1.push(a); q1.push(b); q1.push(c); cout<<"q1:"< A(1,1); pair B(1,2); pair C(2,0); q2.push(A); q2.push(B); q2.push(C); cout<<"q2:"<

进阶2：自定义优先队列
#include #include #include #include using namespace std; //__________方法1：在结构体里重载运算符________ typedef struct Node{ int sum,id; friend bool operator<(Node a,Node b){ return a.sum>b.sum; //通过属性sum建立小顶堆 } }Node; priority_queue q1; /* 关于结构体重载运算符和优先队列定义的解释： priority_queue q1是默认定义方式，我们知道默认的应该是大顶堆，堆排序构建大顶 堆时，应该是当前节点小于（左、右）孩子，才进行交换，所以默认的运算符是'<'，所以在结构体 重载运算符时，应该是friend bool operator<(Node a,Node b)。 而我们想实现通过sum建立小顶堆，所以重载'<'时，把真正的比较对象置为'>','>'是构建小顶 堆，所以使用默认方式建立优先队列，本来要读'<',实际上读的是'>',就简化了书写。（笑，这种方 法太坏蛋了） *///_________________方法2：重写仿函数__________________ typedef struct Node2{ int id,sum; }Node2; struct cmp{ bool operator()(const Node2 a,const Node2 b){ return a.sum,cmp >q2; int main() { //测试样例1 Node a,b,c; a.id = 1; a.sum = 10; b.id = 2; b.sum = 3; c.id = 3; c.sum = 6; q1.push(a); q1.push(b); q1.push(c); cout<<"q1:"<


    推荐阅读


    上一篇：图像处理|信用卡数字识别（opencv，代码分析）

    下一篇：ACM学习|ACM部分学习路线