1 #include <stdio.h>  2 #include <stdlib.h>  3   4 void build_heap(int data[], int);  5 void adjust_heap(int data[], int);  6 void heap_sort(int data[], int);  7 int sub_max_heap(int data[], int, int);  8   9 int main(int argc, char *argv[]) 10 { 11     int i; 12     int data[12] = {6, 10, 3, 5, 12, 8, 4, 23, 1, 2, 9, 7 }; 13  14     heap_sort(data, 12); 15  16     for (i = 0; i < 12; ++i) 17     { 18         printf("%d ", data[i]); 19     } 20  21     printf("\n"); 22     return 0; 23 } 24  25 void heap_sort(int data[], int num) 26 { 27     int i = 1; 28     build_heap(data, num); 29  30     for (i = 1; i < num; ++i) 31     { 32         int temp; 33         temp = data[0]; 34         data[0] = data[num - i]; 35         data[num - i] = temp; 36  37         adjust_heap(data, num - i);     38     } 39  40 } 41  42  43 void build_heap(int data[], int num) 44 { 45     int i, k, p; 46  47     for (i = num / 2 - 1; i >= 0; --i) 48     { 49         k = sub_max_heap(data, num, i); 50         if (k == i) 51             continue; 52  53         while (2 * k + 1 < num) 54         { 55             p = k; 56             k = sub_max_heap(data, num, p); 57             if (k == p) 58                 break; 59         } 60     } 61  62 } 63  64  65 void adjust_heap(int data[], int num) 66 { 67     int temp; 68     int k, p; 69  70     k = 0; 71     while(2 * k + 1 < num) 72     { 73         p = k; 74         k = sub_max_heap(data, num, p); 75         if (k == p) 76             break; 77     } 78  79  80 } 81 /* 82 int sub_max_heap(int data[], int num, int i) 83 { 84     int k; 85  86     if (2 * i + 2 <= num - 1 && data[2 * i + 1] > data[2 * i + 2]) 87         k = 2 * i + 1; 88     else if (2 * i + 2 <= num - 1) 89         k = 2 * i + 2; 90     else 91         k = 2 * i + 1; 92  93     if (data[k] > data[i]) 94     { 95         int temp; 96         temp = data[k]; 97         data[k] = data[i]; 98         data[i] = temp; 99     }100     101     return k;102 103 }104 */105 106 int sub_max_heap(int data[], int num, int i)107 {108     int largest;109     int l, r;110 111     l = 2 * i + 1;112     r = 2 * i + 2;113     114     if (l <= num - 1 && data[l] > data[i])115         largest = l;116     else117         largest = i;118     119     if (r <= num - 1 && data[r] > data[largest])120         largest = r;121     if (largest != i)122     {123         int temp;124         temp = data[i];125         data[i] = data[largest];126         data[largest] = temp;127     }128 129     return largest;130 }