详解：
http://www.ahalei.com/thread-5028-1-2.html
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 }
大顶堆
转载于:https://www.cnblogs.com/zhaopAC/p/5022278.html
相关资源：JAVA上百实例源码以及开源项目
