重载运算符

我们知道优先队列默认是大根堆，而如果想要使用小根堆可以加上 greater。若是处理结构体呢？如何定义优先级呢？

对于结构体而言，将结构体放入优先队列中，比较函数需要建立在针对结构体的具体成员。

有一个非常重要的点，优先队列只能重载小于运算符，不能重载大于运算符。原因是 priority_queue 中默认的比较函数为 less，less 函数中只用到了 { return __x<__y; }，所以重载中若只重载了 \(>\)，函数找不到 \(<\)，所以会出现错误。

这里讲一下自定义优先级的 3 种方法。

以函数成员重载

把重载运算符写到一个单独的 bool 函数里，与 sort 排序的自定义 cmp 比较类似。下面是大根堆的写法：

#include

#include

#include

using namespace std;

struct node

{

int id,val;

};

bool operator < (const node& a,const node& b)//大根堆

{

return a.val

}

priority_queue q;

int main()

{

q.push({1,5});

q.push({2,2});

q.push({3,3});

printf("%d",q.top().val);

return 0;

}

小根堆：

bool operator < (const node& a,const node& b)//小根堆

{

return a.val>b.val;//将val的值从小到大排列，形成node的小根堆

}

自定义比较函数

struct cmp//大根堆

{

bool operator()(const node& a,const node& b)

{

return a.val

}

};

priority_queue,cmp> q;

struct cmp//小根堆

{

bool operator()(const node& a,const node& b)

{

return a.val>b.val;

}

};

priority_queue,cmp> q;

前两种相对来说比较好记，技巧是重载函数内的符号与 sort 的 cmp 恰好相反。只需要记得传入格式是 const node&。

以类成员函数重载

这种看起来和前面两种不太一样，传入的参数少了一个。其实也有一个记住的技巧，就是可以理解为我们少传入的那个是原来的 a，然后我们只需要把里面的 a.val 之类的东西改成 val 就好了，另外记得后面还有一个 const 呀。

struct node

{

int id,val;

//大根堆

bool operator < (const node& b) const//注意这里也有一个const

{

return val

}

};

priority_queue q;

struct node

{

int id,val;

//小根堆

bool operator < (const node& b) const//注意这里也有一个const

{

return val>b.val;

}

};

priority_queue q;