排序(6):堆排序

  • 8
  • 2,722 °C
  • A+
所属分类:技术分享 算法基础
摘要

堆排序是利用堆的性质进行的一种选择排序。

排序(6):堆排序

一、前言

堆排序是一种选择排序。

选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

二、算法思想

堆排序是利用堆的性质进行的一种选择排序。

动态效果示意图:

排序(6):堆排序

是一棵顺序存储完全二叉树

  • 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆
  • 其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为根堆

举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:

  • Ri <= R2i+1  Ri <= R2i+2 (小根堆)
  • Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,,n/2向下取整;

排序(6):堆排序

如上图所示,序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个结点,元素3和元素8

元素3在数组中以R[0]表示,它的左孩子结点是R[1],右孩子结点是R[2]。

元素8在数组中以R[1]表示,它的左孩子结点是R[3],右孩子结点是R[4],它的父结点是R[0]。可以看出,它们满足以下规律

设当前元素在数组中以R[i]表示,那么,

(1) 它的左孩子结点是:R[2*i+1];

(2) 它的右孩子结点是:R[2*i+2];

(3) 它的父结点是:R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

首先,按堆的定义将数组R[0..n]调整为堆(这个过程称为创建初始堆),交换R[0]和R[n];

然后,将R[0..n-1]调整为堆,交换R[0]和R[n-1];

如此反复,直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作:

(1)根据初始数组去构造初始堆(构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大)。

(2)每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后,这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下,如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

排序(6):堆排序

构造了初始堆后,我们来看一下完整的堆排序处理:

还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

排序(6):堆排序

相信,通过以上两幅图,应该能很直观的演示堆排序的操作处理。 

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

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

其实这是有一个公式的,设二叉树结点总数为 n,则最后一个非叶子结点是第 ⌊n/2⌋ 个。

 

1、代码

C++:

运行结果如下:

排序(6):堆排序

Python:

运行结果同上。

三、算法分析

1、堆排序算法的总体情况

排序(6):堆排序

2、时间复杂度

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

n 个结点,从第 0 层至第 logn 层。对于第 i 层的 2i 个点如果需要往下走 logn−i 步,那么把走的所有步相加得:

排序(6):堆排序

接下来就是排序的时间,即下面的代码:

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

堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树,而完全二叉树通常采用顺序存储方式。

当想得到一个序列中第k个最小的元素之前的部分排序序列,最好采用堆排序。

3、算法稳定性

堆排序是一种不稳定的排序方法。

因为在堆的调整过程中,关键字进行比较和交换所走的是该结点到叶子结点的一条路径,因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。 

 

本站整理自:

http://www.cnblogs.com/jingmoxukong/p/4303826.html

https://61mon.com/index.php/archives/202/

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:8   其中:访客  4   博主  4

    • avatar 到底对不对 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 上海理工大学 4

      18行的break是跳出while循环吗?为啥呢?此时仅仅是当前父节点大于左右子节点啊,为啥不继续向下调整而直接跳出?

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点

          @到底对不对 直接退出while循环啊 ,因为已经找到不满足要求的两个节点了,对它们进行调整。

        • avatar 示波器 来自天朝的朋友 谷歌浏览器 Windows 10 安徽省合肥市 中国科学技术大学 1

          循环建立初始堆时,最后一个非叶子结点不是length/2-1吗,比如示例用length/2=7/2=3,即向HeapAdjust传递参数parent=3,那么child=7,显然不满足条件child<length;虽然最终结果不会出错,但这样就多循环了一次

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

              @示波器 非叶子结点是n/2啊。

            • avatar 示波器 来自天朝的朋友 谷歌浏览器 Windows 10 安徽省合肥市 中国科学技术大学 1

              按照你代码上的函数给出的数组arr{6, 4, 8, 9, 2, 3, 1},length=7,那么HeapAdjust函数中参数parent传递的值不就是length/2==7/2=3,而arr[3]=9,9是叶子结点,arr[2]=8,8不应该才是最后一个非叶子结点 吗

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

                  @示波器 哦哦,明白你的意思了,感谢。堆调整那里多调整一次,代码已更改。

                • avatar 示波器 来自天朝的朋友 谷歌浏览器 Windows 10 安徽省合肥市 中国科学技术大学 1

                  在HeadSort函数中,每次进行最后一元素与第一元素交换后,C++版46行只是单一的从根节点往下进行了一次上浮调整,而不是从最后一个非叶子结点开始重新建立大根堆,这样做会出现问题吗;按照楼主前面说的“每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。”,不是应该重新调整为大根堆吗,这里怎么只进行了一次从根节点往下的上浮调整

                    • avatar Jack Cui Admin 来自天朝的朋友 火狐浏览器 Windows 10 辽宁省沈阳市 联通

                      @示波器 调整堆,就是进行一次这样的上浮调整就可以了啊。初始化堆的时候,需要进行length/2次的调整。