1 /*
 2  *Author: ZhangHaiba
 3  *Date: 2014-1-12
 4  *File: heap_sort.c
 5  *
 6  *a demo of heap data struct and heap sort
 7  */
 8 #include <stdio.h>
 9 #define N 512
10 
11 //public
12 void repair_heap(int*, int, int);
13 void create_heap(int*, int);
14 void heap_sort(int*, int);
15 //private
16 void swap(int*, int*);
17 
18 int heap[N];
19 
20 int main(void)
21 {
22     int n;
23 
24     scanf("%d", &n);
25     set_array(heap, n);
26     create_heap(heap, n);
27     heap_sort(heap, n);
28     return 0;
29 }
30 
31 void repair_heap(int *h, int n, int par)
32 {
33     int pmin, save, left, right;
34 
35     while (par <= n/2) {
36         save = h[par];
37         pmin = par; //now point to par
38         left = par*2;
39         right = left+1;
40         if (h[left] < h[par])
41             h[par] = h[pmin = left]; //now point to left
42         if (right <= n && h[right] < h[par])
43             h[par] = h[pmin = right]; //now point to right
44         if (pmin == par) //if ture means par point to root of a heap
45             break;
46         else
47             h[pmin] = save; //swap fininsed
48         par = pmin;
49     }
50 }
51 
52 void create_heap(int *h, int n)
53 {
54     int i;
55     
56     for (i = n/2; i != 0; --i)
57         repair_heap(h, n, i);
58 }
59 
60 //after heap sort, original heap becomes a descending array
61 //in this procession, we output a ascending order of heap data;
62 void heap_sort(int *h, int n)
63 {
64     while (n != 0) {
65         printf(n == 0 ? "%d\n" : "%d ", h[1]);
66         swap(&h[1], &h[n--]);
67         repair_heap(h, n, 1);
68     }
69 }
70 
71 //set array range [1, n]
72 int set_array(int *a, int n)
73 {
74     int i;
75     
76     for (i = 1; i <= n; ++i)
77         scanf("%d", a+i);
78 }
79 
80 void swap(int *a, int *b)
81 {
82     int tmp = *a;
83     *a = *b;
84     *b = tmp;
85 }