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

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

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

下面举个例子(资源来自堆排序-海子)来说明堆排序的过程(以升序为例):

(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)$。

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-10-14
原文链接:https://ethsonliu.com/2019/10/heap-sort.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。