关于优先队列中结构体(struct)中重载运算符(operator)的问题

· · 算法·理论

在学Dijkstra的priority_queue的时候，对结构体的重载运算符一头雾水，故来整理一下，为了我也为了后人。

首先来看看常见的写法： 这种最最最常见的，注意两个比较值的位置

operator < (const node &a)const
{
    return n_dis>a.n_dis;
}

类比sort的cmp，在cmp中是降序排序，大的在前面，而在优先队列里面就变成了小根堆，为什么？

利用STL的priority_queue的默认大根堆特性，我们重载运算符后优先队列不知道，他还是把大的放在前面，小的放在后面，而我们更改了这个大小的定义，让他反了过来，这样，优先队列以为的大数，实际上是小数，所以实现了小根堆。 当然你要是加个greater就弄回去了，更别说加个负号。

第二种，

q.push(make_pair(-d[y],y))

用pair这东西默认按第一个先排序，同样利用priority_queue的大根堆特性，放一个负的进去，大的变小，小的变大，而我们取出使用的下标取原数据，所以没有影响

2024-07-19 福建长乐一中 SpringQin