STL--priority_queue--自定义数据类型

STL中priority_queue的声明模板有3个参数priority_queue<Type,Container,Functional>。

当使用的数据类型Type为自定义数据类型时有以下3种方法。

1)写仿函数

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 struct Node
 5 {
 6     int x,y;
 7 };
 8 struct cmp
 9 {
10     bool operator()(Node a,Node b)
11     {
12         if(a.x!=b.x)
13             return a.x<b.x;//<为大顶堆，>为小顶堆
14         return a.y<b.y;
15     }
16 };
17 int main()
18 {
19     Node node[9]={{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
20     //建立9个结点
21     priority_queue <Node,vector<Node>,cmp> q(node,node+9);//将9个点存入优先队列q
22     while(!q.empty())//输出
23     {
24         Node n=q.top();
25         cout<<n.x<<' '<<n.y<<endl;
26         q.pop();
27     }
28     return 0;
29 }

2)数据类型外重载operator<

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 struct Node
 5 {
 6     int x,y;
 7 };
 8 bool operator<(Node a,Node b)
 9 {
10     if(a.x!=b.x)
11         return a.x<b.x;//<为大顶堆，>为小顶堆
12     return a.y<b.y;
13 }
14 int main()
15 {
16     Node node[9]={{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
17     //建立9个结点
18     priority_queue <Node> q(node,node+9);//将9个点存入优先队列q
19     while(!q.empty())//输出
20     {
21         Node n=q.top();
22         cout<<n.x<<' '<<n.y<<endl;
23         q.pop();
24     }
25     return 0;
26 }

3)数据类型内重载operator<

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 struct Node
 5 {
 6     int x,y;
 7     bool operator<(const Node a)const
 8     {
 9         if(x!=a.x)
10             return x<a.x;
11         return y<a.y;
12     }
13 };
14 int main()
15 {
16     Node node[9]={{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
17     //建立9个结点
18     priority_queue <Node> q(node,node+9);//将9个点存入优先队列q
19     while(!q.empty())//输出
20     {
21         Node n=q.top();
22         cout<<n.x<<' '<<n.y<<endl;
23         q.pop();
24     }
25     return 0;
26 }