9.5 堆排序在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们介绍堆排序

对比选择排序相比较而言

堆排序最大的优点是，只需要一个记录大小的辅助空间

每个待排序的记录也仅占一个存储空间

先给出堆的定义

堆是n个元素的关键字序列

设关键词序列，为k1k2到kn

当且仅当满足以下关系时，称之为堆

如果关键字序列中，排在第i个位置的关键字是ki

ki小于等于序列中2i这个位置的关键字k2i

也小于等于2i+1这个位置的关键字k2i+1

如果序列中所有关键字，都满足这个关系

这样的关键字序列称之为小顶堆

反之，如果ki是大于等于k2i和k2i+1，称之为大顶堆

从堆的定义来看，堆是一个关键字序列

只不过序列中的关键字之间满足一定的关系

回忆完全二叉树的性质5和完全二叉树的顺序存储

可以把堆看成一个顺序存储的完全二叉树

后续讨论中，我们会把堆表现为完全二叉树的样子

并借助二叉树的术语讨论堆

但是，同学们要注意：堆是一个序列

表现为二叉树的样子只是为了直观观察，不要混淆

幻灯片上给出了两个堆的示例

一个大顶堆

一个小顶堆

有了这样一个堆以后，就可以进行排序了

下面大顶堆为例来说明一下自小到大排序的过程

图1中，是一个包含6个记录的大顶堆，用m表示堆长

为了观察方便，把它表现为完全二叉树

如如图2所示，表现为完全二叉树后

观察堆的性质就比较简单，在大顶堆中

每个分支结点的关键字都比它左右孩子的关键字大

堆中最大的关键字一定在根结点的位置，根也被称为堆顶

如何进行堆排序呢？

我们需要进行多趟筛选，每次筛选

把堆序列中最后一个位置的记录和堆顶最大关键字的记录交换

这样最大关键字已经在排序后的位置

把堆的长度减1，堆中不再包含这位置

交换后，可能不在满足堆的性质

需要进行自上而下的调整

使长度减1的序列重新成为一个堆

这样的调整称为筛选

注意，进行筛选的前提是

除了堆顶关键字不满足性质以外，它的左右子树均是堆

结合例子看一下排序过程

第一趟筛选，堆长m=6

把图1中堆顶记录96和堆序列最后一个记录09进行了交换

结果如图3所示，交换以后

最大关键字96已经在排序后的位置

堆的长度m减1后为5，堆序列是图中绿色这一段

不包含6号单元的记录96

对应的二叉树如图4所示

观察图4，不在是大顶堆，需要进行自上而下的筛选

筛选中，关键的2个参数是s和m

m是堆序列的长度为5，s是筛选开始的位置

这里s等于1

含义是从根开始向下筛选

先把s中的记录09暂存到辅助空间rc中

随后找s左右孩子中关键字较大者

较大者是2号单元的左孩子83

rc中的09小于83，把记录83赋值给序列s号单元位置

这里是把记录83赋值1号单元

2号单元赋值后，重置s等于2

继续向下筛选，同样找s左右孩子中关键字较大者

4号单元38较大，09小于38，38赋值给2号单元

重置s等于4，继续向下筛选

4的左孩子是8号单元，但是堆长m为5

4号单元没有孩子，筛选结束

把rc的记录赋值给s单元

这里是把09赋值4号单元，完成第一趟筛选

经过第一趟筛选，结果如图5所示

对应的完全二叉树如图6所示

观察图6可以看到

此时所有分支节点的关键词满足堆性质

重新获得了长度为5的大顶堆

这时，可以说排好一个记录

就是最大关键字的记录96

要完成整个序列的排序，还需要多趟筛选

第二趟筛选过程和第一趟一样

把当前堆序列中第一个和最后一个记录交换

就是记录83和记录11交换

此时，次大关键字83已经在排序好的位置

堆长m减为4，观察图8，不是大顶堆

同样从s=1开始，进行自上而下的筛选

使之重新成为一个堆，后续过程雷同

堆长每次减1，到堆长为1时结束，完成堆排序

下面看一下筛选算法的实现

把本章第1节定义的类型sqlist另外起个名字heaptype

筛选函数的参数有3个

一个是存储堆序列的结构体H

整型参数s是这趟筛选的开始位置

参数m是这趟筛选堆的大小

首先把筛选开始位置的记录暂存到rc

绿色部分的循环从s开始了自上而下进行筛选

j赋值2*s，指明s的左孩子

如果j小于等于m，说明s至少有左孩子

可以循环筛选

循环中第1个if语句是找出左右孩子中较大者

j

如果有右孩子

并且左孩子j的关键字小于右孩子j+1的关键字

做++j，让j指示右孩子，不满足条件

说明没有右孩子或左孩子关键字大，那么j不变

第2个if语句把rc的关键字

和s左右孩子中较大者j的关键字进行比较

如果rc的关键大于等于j的关键字

那么s单元就是rc中记录适当的位置

直接break中断循环，把rc赋值给H.r[s]，筛选结束

如果第2个if语句条件不成立

就是说j的关键字大于rc的关键字

那么H.r[s]=H.r[j]

把左右孩子中较大记录赋值给s

s重置为j，循环继续进行筛选

如果循环过程中没有从break中断循环

那么最后的s是一个叶子

循环结束后把rc赋值给H.r[s]即可

堆排序需要在待排序序列是堆的前提下才能进行

初始的序列一般不是堆，需要把它构建为堆

初始建堆的方法是：将一个无序序列看成是一个完全二叉树

则最后一个非终端结点是第n/2个记录

由此“筛选”只需从第n/2个记录开始

通过多次调用前面介绍的筛选函数

第1次调用把n/2（向下取整）作为实参传递给筛选函数的形参s

表示从n/2开始向下筛选

第2次把n/2-1作为实参

直到最后一次把1作为实参

从根进行筛选

这次筛选后，将建立一个堆

以图1中的序列为例，建立小顶堆

初始序列中有8个元素，看成完全二叉树的话

最后一个分支结点是8÷2向下取整

是4号关键字为97的记录，如图2红圈中所示

从4号开始向下筛选，参数s=4，堆长m=8

要建小顶堆，97只有1个左孩子49,49小于97

向下筛选后，49到4号单元

97到左孩子的8号单元，结果如图3所示

下一次调用筛选函数，参数s=3

堆长不变m=8，从3号单元向下筛选

s的左右孩子中左孩子13较小

并小于s的关键字65

关键字13的记录赋值给3号单元

65到左孩子的6号单元

经过上述2次筛选调用后

结果如图4所示，继续以s=2s=1两次调用筛选函数

结果如图5所示，对应的堆序列如图6所示

此时小顶堆建立完成

提醒一下，要进行自小到大排序

需要建立大顶堆；要进行自大到小排序

需要建立小顶堆，筛选函数要变化一下

下面看一下堆排序的实现

堆排序的函数主要是有两个循环

第1个循环完成初始化建堆

从i等于最后一个分支结点起，循环到i=1

每次循环调用筛选函数

把i作为实参传递给筛选函数的实参s，进行筛选

第一个循环结束后，初始堆建立

第2个循环完成堆排序

，从i等于堆序列的最后一个位置开始

循环到i=2

每次循环把H.r和H.r[i]交换

此时第i个位置的记录已经在排好序的位置

但是1到i-1之间的序列可能不满足堆的性质

调用筛选函数从s=1进行筛选

注意，堆长m为i-1，堆长减少1

循环到i=2，完成堆排序

堆的应用比较广泛，经常作为一个优先队列来使用

作为优先队列的堆会涉及堆中的插入和删除操作

以大顶堆为例，看一下实现

先看堆插入操作Insert:把待插入元素x加入堆尾

需要的话，向上筛选插入x后，堆长增1

从序列中第i个位置向上筛选

是把第i个位置的关键字和双亲的关键字比较

如果大于则和双亲交换，交换后继续向上

直到小于等于双亲或已经交换到根结点为止

图1是堆长为6的大顶堆

假设插入一个关键字为78的记录

78插入到7号位置，78大于双亲27

把78和27交换，交换后如图2所示

继续向上筛选，78小于双亲96

筛选过程就结束了，完成78的插入

删除操作Delete:删除记录H[i]后

用堆中最后一个记录H[n]替换

根据需要向上或向下筛选

删除后，堆长减1

替换后，考察H[i]和双亲以及孩子的大小关系

向上或向下进行筛选

图1中，假设要删除2号位置的记录83

删除以后，用序列中最后一个记录09来代替它

代替以后的情形如图2所示

此时堆长为5,09小于双亲96

09左右孩子中左孩子较大，是38，09小于38

需要进行向下筛选，使之重新变为堆

好，同学们

关于堆排序我们就介绍到这

下次课再见