<学习笔记> 手打堆模板

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int N;
 9 int h[10010];
10 
11 void heap(int n)
12 {
13     while((n<<1)<=N)
14     {
15         int t=n;
16         if((n<<1)<=N&&h[n<<1]<h[n]) t=n<<1;
17         if((n<<1|1)<=N&&h[n<<1|1]<h[t]) t=n<<1|1;
18         if(t!=n) swap(h[n],h[t]),n=t;
19         else break;    
20     }
21 } 
22 void Make()
23 {
24     for(int i=N/2;i>=1;--i)
25         heap(i);
26 }
27 int top()
28 {
29     return h[1];
30 }
31 void pop()
32 {
33     swap(h[1],h[N]); N--; heap(1); 
34 }
35 void push(int x)
36 {
37     ++N; h[N]=x;
38     int n=N;
39     while((n>>1)>=1)
40     {
41         if(h[n]>h[n>>1]) swap(h[n],h[n>>1]),n>>=1;
42         else break;    
43     }     
44 }
45 bool empty()
46 {
47     if(!N) return true;
48     else return false;
49 }
50 void Sort()
51 {
52     while(N)
53     {
54         printf("%d ",h[1]);
55         pop();
56     }
57 }
58 
59 int main()
60 {
61     scanf("%d",&N);
62     for(int i=1;i<=N;++i)
63        scanf("%d",&h[i]);    
64     Make();
65     Sort();
66     return 0;
67 }