这是博客迁移到kongbai.ug0.ltd WordPress后的第一篇文章 之前文章会择优迁移过来

在百度谷歌寻找许久未果后，我决定亲自研究sort和priority_queue的自定义排序。

想法是从CSP-2021-S的T1上，需要自定义优先队列的排序规则，使每次能取出编号最小且能用的廊桥。但搜索引擎上的大多都是上代码，并没有讲原理。而本篇博客的意义就在于去寻找其自定义排序的原理。

默认优先级

priority_queue<int> q;
sort(a+1,a+n+1);

显然，在没有其它自定义函数/仿函数的情况下，sort的优先级是元素最小的在前面，而priority_queue的优先级是元素最大的在top()。

如下面这一段sort排序的代码，按照了a的升序排序，如果a相等，则按b的升序排序

	#include<bits/stdc++.h>
	#define ps(x,y,z) e[z].a=x;e[z].b=y
	using namespace std;
	struct node{
		int a,b;
	}e[15];
	bool cmp(node x,node y){
		if(x.a==y.a)return x.b<y.b;
		return x.a<y.a;
	}
	int main(){
		ps(1,1,1);
		ps(1,3,2);
		ps(1,2,3);
		ps(2,1,4);
		ps(5,1,5);
		sort(e+1,e+5,cmp);
		for(int i=1;i<6;i++)printf("%d%d\n",e[i].a,e[i].b);
		return 0;
	}

11
12
13
21
51
实际输出

那么我们就可以推敲出sort自定义排序的原理：我们可以想象出来一个＞，即函数里返回的true或false代表着node x的优先级是否大于node y的优先级。比如x.a<y.a返回了一个true，那么说明x的优先级大于y的优先级，所以x在前面，因为x.a<y.a，所以实现了升序排序。

在研究优先队列的比较之前，我们要先了解“堆”这个东西。

百度百科

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

而优先队列是一个二项堆，在默认情况下，其是一个大根堆（越大的元素优先级越高）。

	//优先队列
	#include<bits/stdc++.h>
	#define qp(x,y) c.a=x;c.b=y;q.push(c)
	#define pr cout<<q.top().a<<" "<<q.top().b<<'\n'
	using namespace std;
	struct node{
		int a,b;
	};
	struct cmp{
		bool operator()(node x,node y){//注意这里有两个括号 我刚开始调了很久才发现
			if(x.a==y.a)return x.b<y.b; 
			return x.a<y.a;
		}
	};
	priority_queue<int,vector<node>,cmp>q;
	int main(){
		node c;
		qp(1,1);
		qp(1,2);
		qp(2,1);
		while(!q.empty()){
			pr;q.pop();
		}
		return 0;
	}

2 1
1 2
1 1
实际输出

在这个仿函数中（我理解的仿函数就是结构体里面套了一个operator函数，而operator就是一个函数操作符，可以用来重载运算符<>=等），我们定义了如果x.a==y.a，那么按照b的降序排序，否则按照a的降序排序。

等等！明明代码逻辑判断没变，为什么排序方式发生了“质”的改变？

还记得我刚才提到了比较的优先级吗？sort排序的优先级是可以想象成一个＞，默认是升序排序。我们又知道优先队列默认是降序排序，所以不难想到我们可以把其优先级想象成＜号。举个例子（这里用[a,b]代表node结构体里面的int a,b），[1,1]和[1,2]，其a的值是一样的，所以来判断b的值。因为1＜2，所以这里返回了true，说明[1,1]的优先级＜[1,2]的优先级，所以[1,1]在[1,2]的后面。

因为sort的优先级类似于“＞”，优先队列的优先级类似于“＜”，所以我们大可理解为什么同样的比较逻辑排序的方式却是相反的。

重载运算符

上面提到的自定义排序的方式是通过仿函数，那我们需要再研究下如何通过重载运算符的方式进行自定义排序。

	#include<bits/stdc++.h>
	#define ps(x,y,z) e[z].a=x;e[z].b=y
	using namespace std;
	struct node{
		int a,b;
	}e[15];
	bool operator<(const node& x,const node& y){//加了const修饰代表这里不可被修改，更加安全快捷
		if(x.a==y.a)return x.b<y.b;
		return x.a<y.a;
	}
	// bool operator<(node& x,node& y){//加了&表示这里是一个引用，效果一样但效率更高
		// if(x.a==y.a)return x.b<y.b;
		// return x.a<y.a;
	// }
	// bool operator<(node x,node y){
		// if(x.a==y.a)return x.b<y.b;
		// return x.a<y.a;
	// }
	int main(){
		ps(1,1,1);
		ps(1,3,2);
		ps(1,2,3);
		ps(2,1,4);
		ps(5,1,5);//这里的传参的第三项就可以省略不写了
		sort(e+1,e+5);
		for(int i=1;i<6;i++)printf("%d%d\n",e[i].a,e[i].b);
		return 0;
	}

这个的运行结果跟上面是一样的，我们只不过是把中间的仿函数变成了重载运算符。代码里有三种重载运算符的方式(注释掉了两种)，这三种重载运算符在这里的效果一样，但实际上还是有些区别，可以看代码注释。

等等！(第二次了)这样重载运算符还不够高级。我们可以直接把重载运算符的代码丢到结构体本身里面。

	#include<bits/stdc++.h>
	#define ps(x,y,z) e[z].a=x;e[z].b=y
	using namespace std;
	struct node{
		int a,b;
		bool operator<(const node& x)const{ 
//这里的两个const删掉都不会影响程序运行效果 删掉&在面对大量数据的时候运行时间会变长
			if(a==x.a)return b<x.b;
			return a<x.a;
		}
	}e[15];
	int main(){
		ps(1,1,1);
		ps(1,3,2);
		ps(1,2,3);
		ps(2,1,4);
		ps(5,1,5);
		sort(e+1,e+5);
		for(int i=1;i<6;i++)printf("%d%d\n",e[i].a,e[i].b);
		return 0;
	}

看到这里，你应该可以恍然大悟。显然 operator的后面从()变成了＜，如果这里是＞的话会CE。 这里是重点，虽然我说sort排序类似于“＞”，但实际重载的时候需要重载“<”，不然还是会编译错误。

note:   'const node' is not derived from 'const std::reverse_iterator<_Iterator>'
       { return __x < __y; }

接下来是优先队列将重载运算符放在结构体本身里的代码，在结构体外的重载运算符代码跟sort类似，可自行Coding这里就不举例了。

	#include<bits/stdc++.h>
	#define qp(x,y) c.a=x;c.b=y;q.push(c)
	#define pr cout<<q.top().a<<" "<<q.top().b<<'\n'
	using namespace std;
	struct node{
		int a,b;
		bool operator<(const node& x)const{
			if(a==x.a)return b<x.b;
			return a<x.a;
		}
	};
	priority_queue<int,vector<node>>q;
	int main(){
		node c;
		qp(1,1);
		qp(1,2);
		qp(2,1);
		while(!q.empty()){
			pr;q.pop();
		}
		return 0;
	}