排序（3）：堆排序

堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。

堆实际上是一棵完全二叉树，其满足性质：任何一结点大于等于或者小于等于其左右子树结点。

堆分为大顶堆和小顶堆，满足“任何一结点大于等于其左右子树结点”的称为大顶堆，满足“任何一结点小于等于其左右子树结点”的称为小顶堆。由上述性质可知：大顶堆的堆顶肯定是最大的，小顶堆的堆顶是最小的。

下面举个例子（资源来自堆排序-海子）来说明堆排序的过程（以升序为例）：

（1）

给定整型数组：{ 16, 7, 3, 20, 17, 8 }，根据该数组“构建”完全二叉树（并不是真的写代码去构建，只是把数组看成完全二叉树去操作）。

程序从最后一个非叶子结点开始，即3。判断其左右孩子：8，8比3大，把8调整上去。

（2）

3结点下无孩子，判断结束。

继续往前一步，至7结点，判断其左右孩子：20和17，20是最大的，将其调整上去。

（3）

7结点下无孩子，判断结束。

继续往前一步，至16结点，判断其左右孩子：20和8，20是最大的，将其调整上去。

（4）

判断16结点下左右孩子：7和17，17是最大的，将其调整上去。

（5）

16结点下无孩子，判断结束。

遍历已至头部，结束。

（6）至此数组已经满足大顶堆的性质，接下来的操作就很简单了。

看完上面所述的流程你至少有两个疑问：

• 如何确定最后一个非叶子结点？

  其实这是有一个公式的，设二叉树结点总数为n，则最后一个非叶子结点是第$⌊\\frac n2⌋$个。

• 数组当中如何确定当前结点的左右孩子位置？

  设当前结点下标是i，则其左孩子的下标是2i，右孩子的下标是2i+1。请注意：这是建立在数组下标从1开始的情况。若数组下标从0开始，则其左右孩子下标还各需多加一个1。

以下代码默认数组下标从1开始，请读者注意。

/* 已知 array[left]...array[right] 的值除 array[left] 之外均满足堆的定义，
本函数调整 array[left]，使 array[left]...array[right] 成一个大顶堆 */
void HeapAdjust(int array[], int left, int right)
{
    int index = left;

    for (int i = left * 2; i <= right; i = i * 2)
    {
        if (i < right && array[i] < array[i + 1])  // 找到孩子中较大者
            i++;
        if (array[index] > array[i])
            return;
        swap(array[index], array[i]);
        index = i;
    }
}

void HeapSort(int array[], int left, int right)
{
    int len = right - left + 1;

    for (int i = len / 2; i >= left; i--)  // 把数组调整成大顶堆
        HeapAdjust(array, i, right);

    for (int i = right; i > left; i--)     // 排序
    {
        swap(array[left], array[i]);
        HeapAdjust(array, left, i - 1);
    }
}

时间复杂度为$O(nlogn)$，证明如下。

首先计算建堆的时间，也就是下面的代码，

for (int i = len / 2; i >= left; i--)  // 把数组调整成大顶堆
    HeapAdjust(array, i, right);

n个结点，从第0层至第$log\_2n$层。对于第i层的$2^i$个点如果需要往下走$log\_2n-i$步，那么把走的所有步相加得，

$$\begin{align} T(n)&=\sum_{i=0}^{i=log_2n}{2^i(log_2n-i)}\\ &=2n-log_2n-2\\ &<2n\\ &=O(n) \end{align}$$

接下来就是排序的时间，即下面的代码：

for (int i = right; i > left; i--)  // 排序
{
    swap(array[left], array[i]);
    HeapAdjust(array, left, i - 1);
}

HeapAdjust()耗时$logn$，共n次，故排序时间为$O(nlogn)$。

综上所述，堆排序时间复杂度为$T(n)=O(n)+O(nlogn)=O(nlogn)$。