1 //堆
2 #include <stdio.h>
3
4 int h[101]; //用来存放堆的数组
5 int n; //用来存储堆中元素的个数，也就是堆的大小
6
7 //建立堆
8 void creat() {
9 int i;
10 //从最后一个非叶节点到第1个结点依次进行向上调整
11 for (i = n / 2; i >= 1; i--) {
12 siftdown(i);
13 }
14 }
15
16 //删除最大的元素
17 int deletemax() {
18 int t;
19 t = h[1]; //用一个临时变量记录堆顶点的值
20 h[1] = h[n]; //将堆的最后一个点赋值到堆顶
21 n--; //堆的元素减少1
22 siftdown(1); //向下调整
23 return t; //返回之前记录的堆的顶点的最大值
24 }
25
26 //向下调整
27 void siftdown(int i) { //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始开始向下调整
28 int t, flag = 0; //flag用来标记是否需要继续向下调整
29 //当i结点有儿子（其实是至少有左儿子）且需要继续调整时，循环
30 while (i * 2 <= n && flag == 0) {
31 //首先判断它和左儿子的关系，并用t记录较小的结点编号
32 if (h[i] > h[i * 2])
33 t = i * 2;
34 else
35 t = i;
36 //如果它有右儿子，再对右儿子进行讨论
37 if (i * 2 + 1 <= n) {
38 //如果右儿子的值更小，更新较小的结点编号
39 if (h[t] > h[i * 2 + 1])
40 t = i * 2 + 1;
41 }
42 //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的
43 if (t != 1) {
44 swap(t, i); //交换它们
45 i = t; //更新i为刚才与它交换的二子结点的编号，便于接下来继续向下调整
46 } else
47 flag = 1; //否则说明当前的父结点已经比两个子结点都小，不需要进行调整
48 }
49 }
50
51 //交换函数，用来交换堆中的两个元素的值
52 void swap(int x, int y) {
53 int t;
54 t = h[x];
55 h[x] = y;
56 y = t;
57 }
58
59 int main() {
60 int i, j, num;
61 //读入要排序的数字的个数
62 scanf("%d", &num);
63
64 for (i = 1; i <= num; i++)
65 scanf("%d", &h[i]);
66 n = num;
67
68 //建堆
69 creat();
70
71 //删除顶部元素，连续删除n次，其实也就是从大到小把数输出出来
72 for (i = 1; i <= num; i++)
73 printf("%d ", deletemax());
74
75 return 0;
76 }