from -> introdution to algorithm
贴一个带有部分注释的代码
1 #include <stdio.h>
2 #include <string.h>
3 int a[100], heapsize, n;
4 int left(int i){//返回左儿子编号
5 return i * 2;
6 }
7 int right(int i){//返回右儿子编号
8 return i * 2 + 1;
9 }
10 int father(int i){
11 return i / 2;
12 }
13 int heapfy(int i){
14 int l = left(i), r = right(i), largest = i, t;
15 if(l <= heapsize && a[i] < a[l])largest = l;//选取最大的下标
16 if(r <= heapsize && a[largest] < a[r])largest = r;
17 if(largest != i){//若不是当前节点，则证明违反了堆的性质，交换后满足，然后继续维护交换后的子树
18 t = a[i];
19 a[i] = a[largest];
20 a[largest] = t;
21 heapfy(largest);
22 }
23 }
24
25 void make_heap(){//make heap
26 int i;
27 for(i = n / 2; i >= 1; i--)heapfy(i); //由满二叉树的性质决定，x > n / 2 为叶子节点，叶子节点不用维护堆的性质，直接就是一个根，堆性质正确，还要自底向上的一个维护，保证对于一棵树来说，子树已经是堆，这样到跟节点后，整个树就是堆了。
28 }
29
30 void pop_heap(){//将当前堆最大(小)的元素弹出， 和heapsize元素交换，然后堆长度--，交换后只有根有可能违反堆的性质，维护一下。
31 int t;
32 t = a[1];
33 a[1] = a[heapsize];
34 a[heapsize] = t;
35 heapsize--;
36 heapfy(1);
37 }
38
39 int main(){
40 freopen("heap_sort.in", "r", stdin);
41 freopen("heap_sort.out", "w", stdout);
42 int i, j, k;
43 while(scanf("%d", &n) != -1){
44 heapsize = n;
45 for(i = 4; i <= n; i++)scanf("%d", &a[i]);
46 make_heap();
47 for(i = 1; i <= n; i++){
48 pop_heap();
49 }
50 for(i = 1; i <= n; i++){
51 printf("%d ", a[i]);
52 }
53 puts("");
54 }
55 return 0;
56 }
57