最大堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：

父节点i的左子节点在位置 (2*i+1);

父节点i的右子节点在位置 (2*i+2);

子节点i的父节点在位置 floor((i-1)/2);

在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：

最大堆调整（Max_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点

创建最大堆（Build_Max_Heap）：将堆所有数据重新排序

堆排序（HeapSort）：移除位在第一个数据的根结点，并做最大堆调整的递归运算

  1 #include <stdio.h>
  2 
  3 void SwapValue(int *OperatorA, int *OperatorB)
  4 {
  5     if ((NULL == OperatorA) || (NULL == OperatorB))
  6     {
  7         printf ("Invalid Parameter(s)!\n");
  8         return;
  9     }
 10 
 11     if ((*OperatorA) != (*OperatorB))
 12     {
 13         *OperatorA ^= *OperatorB;
 14         *OperatorB ^= *OperatorA;
 15         *OperatorA ^= *OperatorB;
 16     }
 17 }
 18 
 19 // 最大堆排序，升序
 20 // 向上调整成最大堆
 21 void MaxHeapFixUp(int *a, int l)
 22 {
 23     if ((NULL == a) || (l < 0))
 24     {
 25         printf ("Invalid Parameter(s)!\n");
 26         return;
 27     }
 28 
 29     int nTemp = a[l];
 30     int i = l;
 31     int j = (i - 1) / 2;
 32 
 33     while (j >= 0)
 34     {
 35         if (a[j] >= nTemp)
 36         {
 37             break;
 38         }
 39 
 40         a[i] = a[j];
 41         i = j;
 42         j = (i - 1) / 1;
 43     }
 44 
 45     a[i] = nTemp;
 46 }
 47 
 48 // 简化代码的向上调整
 49 void MaxHeapFixUp1(int *a, int l)
 50 {
 51     if ((NULL == a) || (l < 0))
 52     {
 53         printf ("Invalid Parameter(s)!\n");
 54         return;
 55     }
 56 
 57     int nTemp = a[l];
 58     int i;
 59     int j;
 60     
 61     for (i = l, j = (i - 1) / 2; (j >= 0) && (a[j] < nTemp); i = j, j = (i - 1) / 2)
 62     {
 63         SwapValue (&a[i], &a[j]);
 64     }
 65 }
 66 
 67 // 向下调整
 68 void MaxHeapFixDown(int *a, int l, int N)
 69 {
 70     if ((NULL == a) || (l < 0) || (l >= N))
 71     {
 72         printf ("Invalid Parameter(s)!\n");
 73         return;
 74     }
 75 
 76     int nTemp = a[l];
 77     int i = l;
 78     int j = 2 * i + 1;
 79 
 80     while (j < N)
 81     {
 82         if (((j + 1) < N) && (a[j+1] > a[j]))
 83         {
 84             ++j;
 85         }
 86 
 87         if (a[j] <= nTemp)
 88         {
 89             break;
 90         }
 91 
 92         a[i] = a[j];
 93         i = j;
 94         j = 2 * i + 1;
 95     }
 96 
 97     a[i] = nTemp;
 98 }
 99 
100 // 将数组转换成最大堆存储
101 void ShiftToMaxHeap(int *a, int N)
102 {
103     if ((NULL == a) || (N <= 0))
104     {
105         printf ("Invalid Parameter(s)!\n");
106         return;
107     }
108 
109     for (int i = N / 2 - 1; i >= 0; --i)
110     {
111         MaxHeapFixDown (a, i, N);
112     }
113 }
114 
115 // 最大堆排序
116 void MaxHeapSort(int *a, int N)
117 {
118     if ((NULL == a) || (N <= 0))
119     {
120         printf ("Invalid Parameter(s)!\n");
121         return;
122     }
123 
124     for (int i = N - 1; i >= 1; --i)
125     {
126         SwapValue (&a[0], &a[i]);
127         MaxHeapFixDown (a, 0, i);
128     }
129 }
130 
131 int main(void)
132 {
133     int a1[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
134 
135     MaxHeapSort (a1, 9);
136 
137     for (int i = 0; i < 9; ++i)
138     {
139         printf ("%d ", a1[i]);
140     }
141 
142     printf ("\n");
143 
144     return 0;
145 }