全屏显示专题章节

堆排序（heap　sort）是堆积排序的简称,是在选择排序的基础上发展起来的,它比选择排序的效率要高。堆积排序方法除了是一种排序方法,还涉及方法之外的某些概念,如堆积与完全二叉树的概念。

堆排序是另一种基于选择的排序方法,下面首先介绍堆的定义。

堆定义　由n个元素组成的序列{k₁,k₂,…,k_n－1,k_n},当且仅当满足如下关系时,称之为堆。

（1）这些元素是一棵完全二叉树中的结点,并且对于i＝1,2,…,n,k_i是该完全二叉树中编号为i的结点。

（2）k_i≤k_2i（或k_i≥k_2i）　　　　　　　　（1≤i≤?n/2」）

（3）k_i≤k_2i＋1（或k_i≥k_2i＋1）　　　　　　　（1≤i≤?n/2」）

从堆的定义可以看出,堆是一棵完全二叉树,在这棵完全二叉树中每一个非终端结点（分支结点）的元素均大于等于（或小于等于）其左、右孩子结点的元素值。

例如,序列（47,35,26,26,18,7,13,19）满足以下条件:

K₁＝47＞K₂＝35,K₂＝35＞K₄＝26,K₃＝26＞K₆＝7,K₄＝26＞K₈＝19,K₁＝47＞K₃＝26,K₂＝35＞K₅＝18,K₃＝26＞K₇＝13

图9－2（a）和图9－2（b）为堆的两个示例,所对应的元素序列分别为{92,84,25,36,14,07}和{15,39,23,87,44,31,52,90}。

根据堆的定义,可以得出堆的以下性质。

（1）堆的根结点是堆中元素值最小（或最大）的结点,称为堆顶元素。

（2）从根结点到每个叶结点的路径上,元素的排序序列都是递减（或递增）有序的。

（3）大根堆的根结点是堆中值最大的元素,小根堆的根结点是堆中值最小的元素,堆的根结点元素称为堆顶元素。

（4）对于大根堆,从根结点到每个叶子结点路径上的元素组成的序列都是递减（或非递增）有序的；对于小根堆,从根结点到每个叶子结点路径上的元素组成的序列都是递增（或非递减）有序的。

（5）堆中任一子树也是堆。

堆排序就是利用堆顶元素的关键字值最小（或最大）的性质,从当前待排序列中依次选取关键字最小（或最大）的记录来进行选择排序的一种方法,其基本步骤如下。

（1）对一组待排序数据序列,按照堆的定义,创建成一个堆,这时根结点（堆顶元素）具有最小（或最大）值。

（2）取出堆顶记录插入有序区并把剩余记录重新调整成一个新堆。

（3）不断重复执行步骤（2）,直到所有记录全部被插入到有序区为止。

由此可知,在堆排序的过程中,关键是做好以下两方面工作:①如何将给定的待排序记录构成一个初始堆？②取出堆顶元素后,如何将剩余记录调整成一个新堆？为了完成这两方面的工作,通常可以通过一个“筛选”过程来实现。

所谓筛选是指从一个结点到其某个叶子结点的一次调整过程。如果一个结点i的左右子树已满足堆的条件,那么筛选就是将以结点i为根的子树调整为一个堆的过程。其具体方法为:将结点i与其左、右孩子结点进行比较,若结点i的关键字值大于它的任意一个孩子结点的关键字值,则按照堆的定义,将结点i与左右孩子中关键字较小的结点交换位置。然后将该结点继续与新的孩子结点相比较,依此类推,直到该结点为叶子结点或它的关键字值小于等于左、右孩子结点记录的关键字值为止。

在这个筛选算法中,用temp将R[i]的值暂时保存起来,如果再比较的过程中发现temp.key＞R[j].key,则需要交换结点位置,但因为被调整的结点在以后的比较中可能需要多次使用,故这里没有立刻将原R[i]结点放置到孩子结点的位置上去,而仅仅是调整了孩子结点的位置。只有当整个筛选过程全部结束时,才将原来的R[i]放置到合适的位置上。

利用上述筛选算法,可以完成将一个无序记录序列创建成一个堆。对于任意的待排序记录序列{R[1],R[2],…,R[n]},要将它们组织成为一个堆,就必须将它对应的二叉树中的每一个子树都调整成为一个堆。显然,只有一个结点的树是堆,由于第i（n/2）个结点之后的结点无左、右子树,即以第i（n/2）个结点之后的结点为根的子树也必然是堆。因此,以这些结点为孩子的结点,他们的左右子树也是堆,只要对这些结点执行一遍筛选算法就可以使以这些结点为根结点的子树都成为堆。同理,这些结点的直接父结点通过一遍筛选算法就可以转化为堆,如此反复推导,当根结点的孩子结点都经过筛选之后,只需要对堆根结点进行一遍筛选就可使整棵树都转化为堆。因此,只要从i（n/2）个记录到第1个记录依次调用堆排序算法,将完全二叉树筛选一遍,就可以建成一个堆。

接下来讨论在输出关键字值最小的记录后,如何通过筛选算法将剩余记录整理成一个新堆。由于堆的根结点是关键字值最小的记录,在输出根结点之后,堆排序是以序列的最后一个记录作为新的根结点,此时由于原堆的各个子树都是堆,则根结点的左右子树也是堆,此时可利用筛选算法进行依次调整,就可以将剩余记录整理成一个新堆。

根据上述的算法思想,堆排序算法可描述如下。

例如,有一个8个元素的无序序列{56,37,48,24,61,05,16,37},它所对应的完全二叉树及其建堆过程如图9－3所示。因为n＝8,n/2＝4,所以从第4个结点起至第一个结点止,依次对每一个结点进行筛选。

【例9－4】　使用筛选法在如图9－3（f）的堆中进行排序。

调用筛选运算进行堆排序的过程如图9－4（a）～（n）所示。

（1）堆排序对n较大的文件比较有效,记录数n较少时不提倡使用。

（2）堆排序运行的时间主要耗费在建初始堆和调整建新堆的反复筛选上。对深度为K的堆,HeapAdjust算法中进行的关键字比较次数不超过2（K－1）次。n个结点的完全二叉树的深度为log₂n＋1,则调整新建堆时调用HeapAdjust过程n－1次,总共进行的比较次数不超过2×（log₂（n－1）＋log₂（n－2）＋…＋log₂2）。因此,堆排序在最坏的情况下,其时间复杂度也为O（nlog₂n）,相对于快速排序来说,这是堆排序最大的优点。

（3）堆排序的空间复杂度为O（1）,即仅需一个记录大小的辅助存储空间,供交换元素使用。