堆排序是利用堆的数据结构而设计的一种排序算法。堆是一种完全二叉树，它具有以下性质：即每个节点的值总是大于（或小于）它的父结点的值。

我们会用到两种堆：
大顶堆：每个节点都大于或等于它的子节点的值，称为大顶堆。
小顶堆：每个节点都小于或等于它的子节点的值，称为小顶堆。

每个列表都可以按下标顺序表示为一个二叉树，如下图：

heapStruct.png

算法步骤

  1. 构造初始堆（升序用大顶堆，降序用小顶堆）。
  2. 将堆顶元素与列表末尾元素交换，此时列表末尾元素为最大（或最小）。
  3. 将堆长度缩小 １，然后调整整个堆，使其满足堆的性质。
  4. 重复步骤 2, 3, 直到堆长度为１。

动图演示

heapSort.webp

代码示例

#define SORT_OK    (0)
#define SORT_ERR    (-1)

static void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

static void heapAdjust(int* array, int rootIndex, int end)
{
    int value = array[rootIndex];
    int child;

    while ((child = rootIndex * 2 + 1) <= end)
    {
        if (child + 1 <= end && array[child + 1] > array[child])
            child = child + 1;
        if (array[rootIndex] < array[child])
        {
            swap(&array[rootIndex], &array[child]);
            rootIndex = child;
        }
        else
            break;
    }
}

static void buildMaxHeap(int* array, int length)
{
    for (int i = length / 2 - 1; i >= 0; i--)
    {
        heapAdjust(array, i, length - 1);
    }
}

int heapSort(int* array, int arrLen)
{
    if (array == NULL || arrLen < 0)
        return SORT_ERR;
    buildMaxHeap(array, arrLen);
    for (int i = arrLen - 1; i >= 0; i--)
    {
        swap(&array[0], &array[i]);
        heapAdjust(array, 0, i - 1);
    }
}