堆

省选前。发现某题czt的代码又一次奇短无比。。

然后我就学了一个新的stl库。

【根本原因是我正处于并将长期处于C++萌新状态。。来熟练打一句话证明： for i:=1 to n do if i mod 2=1 then blabla....;

priority_queue <int> s[10000]; //首先它的真名叫优先队列，俗称堆

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 priority_queue <int,vector<int>,greater<int> > Q;//  注意greater<int>后面要空一格  不然CE 
 4 /*
 5     若priority_queue <int> Q;   
 6      则默认为 
 7          priority_queue <int,vector<int>,less<int> > Q;  所以默认是大根堆 
 8 */
 9 int a[10]={0,4,1,3,5,3,7,8,24};
10 int main(){
11     for (int i=1;i<10;++i) Q.push(a[i]); //加入堆中 
12     while (!Q.empty()){  //堆是否空 
13         printf("%d
",Q.top()); //返回堆顶的值
14         Q.pop();  //弹出堆顶
15     }
16     return 0;
17 }
18 /*输出：
19 0
20 1
21 3
22 3
23 4
24 5
25 7
26 8
27 24
28 
29 */

那么如果我要自己定义一个元素为node的堆呢？

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int x,y;  
 5 }a[10]={{0,0},{1,2},{-1,4},{6,3},{9,10},{-1,-2},{23,2}};   //struct数组原来可以这么赋初值 
 6 struct cmp{  //这里相当于定义了小于号 而它是大根堆
 7     bool operator()(const node &a,const node &b){
 8         return a.x==b.x?a.y<b.y:a.x<b.x;
 9     }
10 };
11 priority_queue <node,vector<node>,cmp> Q;
12 int main(){
13     for (int i=1;i<10;++i) Q.push(a[i]);
14     while (!Q.empty()){
15         printf("%d,%d
",Q.top().x,Q.top().y);
16         Q.pop();
17     }
18     return 0;
19 }
20 /*输出：
21 23,2
22 9,10
23 6,3
24 1,2
25 0,0
26 0,0
27 0,0
28 -1,4
29 -1,-2
30 
31 */