# 堆排序

@Author: 张海拔

@Update: 2014-01-12

``` 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 }```

1）首先，逻辑关系上它是完全二叉树，物理存储是静态线性表（数组）
2）其次，父母结点的值一定大于(小于)孩子结点的值

1）父母结点的指针范围：[1, n/2]
2）叶子结点的指针范围：[n/2+1, n]
3）左孩子指针可由其父母指针计算：left = par*2;
4）右孩子存在的条件：right <= n;

1）自顶向下调整（可能需要回溯往上调整）
2）自底向上调整（一定顺序往下调整）

pmin指针的意义是指向当前的树根、左子树根和右子树根三者中的值最小的节点。

pmin初始指向par，经过判断，pmin可能指向left，也可能指向right，也可能仍指向par。

(0)
(0)