1 /**
 2  * 小堆 <=> 升序排列
 3  * 从最后一个非叶子结点开始, 向前进行调整
 4  * @param a 待排序序列(数组)
 5  * @param n 待排序元素个数
 6  */
 7 void HeapSort(int a[], int n)
 8 {
 9     // S1 建堆
10     // 从最后一个非叶子结点开始, 向前进行调整
11     for(int i = LocOfLastNonLeaf(a, n); i >= 0; i --)
12     {// LocOfLastNonLeaf : (n-1) / 2
13         HeapAdjust(a, i, n);
14     }
15 
16     // S2 输出并调整
17     for(int j = n-1; j > 0; j --)
18     {// 判断条件不用加"=", 因为j=0时等价于数组只有一个元素, 即只有一个根节点, 而无子树
19         Swap(a[0], a[j]); // 形参为同名参数, 直接交换a[0]和a[j]
20         HeapAdjust(a, 0, j);
21     }
22 }

 1 /**
 2  * 筛选位置i, 调整堆
 3  * @param a 待排序序列(数组)
 4  * @param i 筛选位置
 5  * @param len 数组元素个数
 6  */
 7 void HeapAdjust(int a[], int i, int n)
 8 {
 9     if(i > n / 2 - 1)
10     {// 叶子结点, 无子树
11         return;
12     }
13 
14     // 检查结点i是否符合小堆特性, 如果不符合, 需要与最小子结点交换
15     for(int k = 2*i +1; k < n; k = 2*k + 1)
16     {
17         // 判断右子树是否比左子树更小
18         if(k+1 < n && a[k+1] < a[k])
19         {
20             k ++; // 更新最小子结点
21         }
22 
23         if(a[i] > a[k])
24         {
25             Swap(a[i], a[k]); // 与最小的子结点交换
26             i = k;  // 将左子结点设为当前结点
27         }
28         else
29         {// 符合小堆特性
30             break;
31         }
32     }
33 }

 1 int main()
 2 {
 3     int a[] = {
 4 //            10,2,5,9,5,55,21,33,15
 5             49, 38, 65, 97, 76, 13, 27, 49
 6     };
 7     int a_len = sizeof(a) / sizeof(a[0]);
 8 
 9     printf("原始序列: ");
10     PrintArrary(a, a_len); // 打印数组
11 
12     HeapSort(a, a_len); // 堆排序
13 
14     printf("小堆排序后序列(降序): ");
15     PrintArrary(a, a_len); // 打印数组
16 
17     return 0;
18 }