优先队列
struct sss { int x,y; inline friend bool operator <(const sss &a , const sss &b) { return a.x>b.x; //从大到小排列 } }a[100];
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。
在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。
和队列基本操作相同: top 访问队头元素 empty 队列是否为空 size 返回队列内元素个数 push 插入元素到队尾 (并排序) emplace 原地构造一个元素并插入队列 pop 弹出队头元素 swap 交换内容
第一种: priority_queue<int>q; 举个例子:1 5 7 0 3 4 如果是默认的,什么都不写,是按照从大到小排列的。输出:7 5 4 3 1 0(其他数据类型,一样),(从小到大,下面会讲) 第二种: priority_queue<node>q; 结构体的优先队列与数组不一样,要用到运算符重载来写。 例如: struct node { int x,y; //***特别注意*** //运算符重载,如果是优先队列的排序,下面是按照x,从大到小输出 //如果是sort中的cmp,那就是从小到大排序的 bool operator <(const node &a) const { return x<a.x; //从大到小排序 //或者 return this.h < a.x; } //如果要从小到大输出,要改为return x>a.x; }; 第三种: 第一种提到了,从大到小的输出,它与priority_queue< int,vector,less >q;的功能一样。 而priority_queue< int,vector,greater >q;是从小到大输出的。 运算符重载: 运算符重载为类的成员函数的一般格式为: <函数类型> operator <运算符>(<参数表>) { <函数体> } 下面来进行这段代码的分析: struct node { //定义一个结构体node(节点) int x; int y; int len; //node中有3个成员变量x,y,len bool operator <(const node &a)const {//重载<操作符。可以对两个node使用<操作符进行比较 return len<a.len; } }; 括号中的const表示参数a对象不会被修改,最后的const表明调用函数对象不会被修改! 优先队列中结构体的使用: struct Fx { int x; int f; //喷头的数量 bool operator <(const Fx & a) const {return f > a.f;} // 重构<符号,用于优先队列的排序 Fx(int xx = 0, int ff = 0):x(xx), f(ff){} // 构造函数 用来初始化x,f的值 }; 类的默认复制构造函数和赋值运算符可以复制所有元素。例如: struct Point { int x,y; Point(int xx = 0, int yy = 0) :x(xx), y(yy) { } }; Point p1(1,2); Point p2 = p1;