结构体优先队列

要想使用结构体的优先队列， 需要在结构体内部重载小于号。

struct node { int x, y; bool operator < (const node & a) const { return x<a.x; } };

一个 node 结构体有两个成员，x 和 y，它的小于规则是 x 小者小。

它也是按照重载后的小于规则，从大到小排序的。

priority_queue <node> q; int main() { k.x = 10, k.y = 100; q.push(k); k.x = 12, k.y = 60; q.push(k); k.x = 14, k.y = 40; q.push(k); k.x = 6, k.y = 80; q.push(k); k.x = 8, k.y = 20; q.push(k); while (!q.empty()) { node m = q.top(); q.pop(); printf("(%d,%d) ", m.x, m.y); } }

程序大意就是插入(10,100), (12,60), (14,40), (6,80), (8,20) 这五个 node

再来看看它的输出：

(14,40) (12,60) (10,100) (8,20) (6,80)

就是按照 x 从大到小排序的。

除了重载运算符之外，还有一种方法可以自定义结构体如何比较大小，这需要自己定义一个新的结构体，专门用作比较。

struct node { int to, cost; }; //定义一个专门用作比较的结构体 struct cmp { bool operator() (node a, node b) { return a.cost > b.cost; } }; priority_queue<node,vector<node>, cmp> priq;