1 //删除堆顶之后把最后一个移到堆顶在调整，慢
2
3 #include <iostream>
4 #include <cstring>
5 #include <cstdio>
6 #include <algorithm>
7 using namespace std;
8
9 const int N = 100;
10 int h[N];
11 int n;
12 void shitdow(int i)
13 {
14 int t,flag = 1;
15 while(i * 2 <= n && flag)
16 {
17 if(h[i * 2] < h[i])
18 t = i * 2;
19 else
20 t = i;
21
22 if(i * 2 + 1 <= n)
23 {
24 if(h[t] > h[i * 2 + 1])
25 t = i * 2 + 1;
26 }
27 if( t != i)
28 {
29 swap(h[i],h[t]);
30 i = t;
31 }
32 else
33 flag = 0;
34 }
35 }
36 void create()
37 {
38 for(int i = n / 2; i >= 1; i--)
39 shitdow(i);
40
41 }
42 int deletemax()
43 {
44 int t = h[1];
45 h[1] = h[n];
46 n--;
47 shitdow(1);
48 return t;
49 }
50 int main()
51 {
52 int tn;
53 scanf("%d",&n);
54 for(int i = 1; i <= n; i++)
55 scanf("%d",&h[i]);
56 create();
57 tn = n;
58 for(int i = 1; i <= tn; i++)
59 {
60 printf("%d ",deletemax());
61 }
62
63 return 0;
64 } 小顶堆
1 //堆顶一定是最大的，然后将堆顶跟最后一个交换，更新
2
3 #include <iostream>
4 #include <cstring>
5 #include <cstdio>
6 #include <algorithm>
7 using namespace std;
8
9 const int N = 100;
10 int h[N];
11 int n;
12 void shitdow(int i)
13 {
14 int t,flag = 1;
15 while(i * 2 <= n && flag)
16 {
17 if(h[i * 2] > h[i])
18 t = i * 2;
19 else
20 t = i;
21
22 if(i * 2 + 1 <= n)
23 {
24 if(h[t] < h[i * 2 + 1])
25 t = i * 2 + 1;
26 }
27 if( t != i)
28 {
29 swap(h[i],h[t]);
30 i = t;
31 }
32 else
33 flag = 0;
34 }
35 }
36 void create()
37 {
38 for(int i = n / 2; i >= 1; i--)
39 shitdow(i);
40
41 }
42 void heapsort()
43 {
44 while(n > 0)
45 {
46 swap(h[1],h[n]);
47 n--;
48 shitdow(1);
49 }
50 }
51 int main()
52 {
53 int tn;
54 scanf("%d",&n);
55 for(int i = 1; i <= n; i++)
56 scanf("%d",&h[i]);
57 create();
58 tn = n;
59 heapsort();
60 for(int i = 1; i <= tn; i++)
61 {
62 printf("%d ",h[i]);
63 }
64
65 return 0;
66 } 大顶堆 |
|
收藏
淘帖
踩
