优先队列

优先队列与普通的队列相比好处就在于可以自定义优先级，优先级别高的先出队。

下面附加代码介绍一下优先队列简单的自定义优先级别

1。最大值优先出队

View Code

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 priority_queue<int>qu;
 8 int main()
 9 {
10     int n,i,x;
11     cin>>n;
12     for(i = 0; i < n; i++)
13     {
14         cin>>x;
15         qu.push(x);
16     }
17     while(!qu.empty())
18     {
19         cout<<qu.top()<<endl;
20         qu.pop();
21     }
22     return 0;
23 }

2。最小值优先出队，可用于求解哈夫曼问题

View Code

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 priority_queue<int,vector<int>,greater<int> >qu;
 8 int main()
 9 {
10     int n,i,x;
11     cin>>n;
12     for(i = 0; i < n; i++)
13     {
14         cin>>x;
15         qu.push(x);
16     }
17     while(!qu.empty())
18     {
19         cout<<qu.top()<<endl;
20         qu.pop();
21     }
22     return 0;
23 }

3。自定义一级的优先级别

View Code

4。自定义二级的优先级别

View Code

 1 #include <iostream>
 2 #include <queue>  
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     friend bool operator < (node a,node b) // 不能在自定义 " > " 号。编译通不过
10     {
11         return a.l % 10 < b.l % 10;  // 关键值 l 的个位数越大，优先级别越高
12     }
13     int l;
14     int d;
15 };
16 priority_queue<node>qu;  // 优先队列定义方式
17 int main()
18 {
19     node a[100];
20     int n,i;
21     cin>>n;
22     for(i = 0; i < n; i++)
23     {
24         cin>>a[i].d>>a[i].l;
25         qu.push(a[i]);
26     }
27     while(!qu.empty())
28     {
29         cout<<qu.top().d<<endl;
30         qu.pop();
31     }
32     return 0;
33 }