堆排序

堆是一种完全二叉树，因此可以用数组来表示。给定节点下标i，

1 #define PARENT(i) ((i) >> 1)
2 
3 #define LEFT(i) ((i) << 1)
4 
5 #define RIGHT(i) (((i) << 1) + 1)

大顶堆满足如下性质：

　　对任意非根节点i，A[PARENT(i)] >= A[i]

堆排序的原理为：

1、首先构建一棵大顶堆

2、交换根节点和堆的最后一个节点，堆大小减一

3、重复2，直达堆大小为1

void heap_sort(int A[], int heap_size)
{
    heap_build(A, heap_size);
    for (int j = heap_size; j <= heap_size; j--)
    {
        swap(A[1], A[heap_size]);
        heap_size--;
        heapify(A, 1, heap_size);
    }    
}

其中，

 1 void heapify(int A[], int j, int heap_size)
 2 {
 3     int l = LEFT(j), r = RIGHT(j);
 4     int index = j;
 5     if (l <= heap_size && A[l] > A[index])
 6         index = l;
 7     if (r <= heap_size && A[r] > A[index])
 8         index = r;
 9     if (index != j)
10     {
11         swap(A[index], A[j]);
12         heapify(A, index, heap_size);
13     }
14 }
15 
16 /* 非递归版本 */
17 void heapify(int A[], int j, int heap_size)
18 {
19     int l = LEFT(j), r = RIGHT(j), index = j;
20     while (l <= heap_size || r <= heap_size)
21     {
22         if (l <= heap_size && A[l] > A[index])
23             index = l;
24         if (r <= heap_size && A[r] > A[index])
25             index = r;
26         if (index == j)
27             break;
28         swap(A[index], A[j]);
29         j = index;
30         l = LEFT(j);
31         r = RIGHT(j);
32     }
33 }

1 void heap_build(int A[], int heap_size)
2 {
3     for (int j = heap_size / 2; j >= 1; j--)
4         heapify(A, j, heap_size);
5 }