定义

堆 是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩
子结点的值，称为小顶堆。

堆排序（HeapSort） 就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

例如图下所示，图①是一个大顶堆，90为最大值，将90与20（末尾元素）互换，如图②所示，此时90就成了整个堆序列的最后一个元素，将20经过调整，使得除90以外的结点继续满足大顶堆定义（所有结点都大于等于其子孩子），见图③，然后再考虑将30与80互换...

算法设计思路

需要完成两个问题：

1. 如何由一个无序序列构成一个堆？
2. 如何在输出堆顶元素后，调整剩余元素成为一个新的堆？

构建大顶堆

定义序列
- L = {50,10,90,30,70,40,80,60,20}
- L->length = 9.
- startIndex: 起始调整位置索引
- endIndex: 结束位置索引

从 startIndex = (L->length)/2 开始一直到 endIndex 作调整，因为这些都是有孩子的结点，比如下图: startIndex = 9/2 = 4. 顺序就是 ：4->3->2->1.

1. 所谓的构建大顶堆，就是从上往下，从有到左，将每个非终端结点（非叶结点）当作根节点，将其和其子树调整成大顶堆的过程。我们从 startIndex = 4 开始：
   
   

2. 让 startIndex = 4 的根结点与其子树 （2 * startIndex = 8 和 2 * startIndex+1 = 9）的元素比较，将最大的子树和根结点交换。下图中，最大的是 2 * startIndex = 8 的元素。
   

   

3. 接下来判断 startIndex =3 的根节点，本身就是最大的，不作变化。

4. 根节点（startIndex = 2 ）, 与子树（2*startIndex = 4 和 2 * startIndex+1 = 5 ）比较，2 * startIndex+1 = 5 最大，替换。
   

   
   
   
   

5. 根结点（startIndex = 1），与子树（ 2 * startIndex = 2 和 2 * startIndex+1 = 3 ）比较，2*startIndex+1 = 3 最大，替换，此时子树（i = 7 ） 值为 80 > 50， 再次替换。
   

   

最终得到了大顶堆。

堆排序

定义 i 来控制元素索引。

1. i = 9 的时候，20(i=9) < 90(i=1)，交换元素，然后构建大顶堆。
   
   

2. i = 8 的时候，30(i=8) < 80(i=1),交换元素，然后构建大顶堆。
   

   

3. 后续变化完全一致。
   

   
   
   最终就得到一个完全有序的序列。

算法实现

#include <stdio.h>

#define MAXSIZE 20

typedef struct {
  int array[MAXSIZE];
  int length;
} SqList;

void swap(SqList *L, int i, int j) {
  int temp = L->array[i];
  L->array[i] = L->array[j];
  L->array[j] = temp;
}

/**
 * 调整堆结构，使其满足大顶堆性质
 * @param L 待调整的顺序表
 * @param startIndex 起始调整位置索引
 * @param endIndex 结束位置索引
 */
void HeapAdjust(SqList *L, int startIndex, int endIndex) {
  int holdValue, childIndex;
  holdValue = L->array[startIndex]; /* 记录当前节点值 */

  for (childIndex = 2 * startIndex; childIndex <= endIndex; childIndex *= 2) {
    if (childIndex < endIndex &&
        L->array[childIndex] < L->array[childIndex + 1])
      childIndex++;
    if (holdValue > L->array[childIndex])
      break;

    L->array[startIndex] = L->array[childIndex];
    startIndex = childIndex;
  }
  L->array[startIndex] = holdValue;
}

void HeapSort(SqList *L) {
  int i;
  for (i = L->length / 2; i > 0; i--)
    HeapAdjust(L, i, L->length); /* 构建大顶堆 */

  for (i = L->length; i > 1; i--) {
    swap(L, 1, i); /* 将堆顶元素与当前最后一个元素交换 */
    HeapAdjust(L, 1, i - 1); /* 调整堆结构 */
  }
}

int main(void) {
  SqList L = {{0, 50, 10, 90, 30, 70, 40, 80, 60, 20}, 10};
  printf("排序前：");
  int i;

  for (i = 1; i <= L.length; i++)
    printf("%d ", L.array[i]);
  printf("\n");

  HeapSort(&L);
  printf("排序后：");
  for (i = 1; i <= L.length; i++)
    printf("%d ", L.array[i]);

  return 0;
}

排序前：50 10 90 30 70 40 80 60 20 0 
排序后：0 10 20 30 40 50 60 70 80 90 
[Done] exited with code=0 in 0.407 seconds

复杂度分析

排序阶段总时间复杂度：

循环次数：n-1 次 ≈ n 次
每次迭代时间复杂度：O(1) + O(log n) = O(log n)
总时间复杂度：n × O(log n) = O(n log n)