欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆与堆排序

程序员文章站 2022-07-08 15:58:39
...

引言

在简单选择排序中,我们每一趟比较时并没有将比较的结果保存下来,这样下一趟可能会产生重复的比较,导致效率降低。

如果可以做到每次在选择到最小记录的同时,并根据比较结果对其他记录做出相应的调整,那样排序的总体效率就会非常高了。

下面要介绍的堆排序(Heapsort)就是对简单选择排序的一种改进,是由FloydWilliams在1964年共同发明的,同时,他们发明了"堆"这一数据结构。



堆结构的定义

堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子的结点,称为小顶堆。下图左右分别为小顶堆和大顶堆的示例图

堆与堆排序


由堆的定义知,根结点一定是堆中所有结点最大(小)者。较大的数更靠近根(平均情况,不绝对,如上右图40<70)。

由于堆是一颗完全二叉树,那么按照层序遍历的方式给结点从1开始编号,则结点满足如下关系:

堆与堆排序

这是由完全二叉树性质决定的,其实际说明了下标i与2i和2i+1的双亲子女关系

堆排序就是利用堆这种数据结构进行排序的。



堆排序算法

堆排序(Heap Sort)就是利用堆(下面以大顶堆为例进行介绍)进行排序的方法。它的基本思想是,将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的元素了。将它与堆数组的最后一个元素进行交换,并让前n-1个元素从新构成一个堆的结构,这样就会得到n个元素的次大值。如此执行下去,便得到一组有序的序列。如下图①②③

堆与堆排序

堆与堆排序


堆与堆排序


基本思想如上,下面我们分析子问题,可以概括为两步:

1.由一个无序序列构成一个堆

2.在交换堆顶元素后,调整剩余元素为一个堆


下面根据代码来分析

void HeapSort(Sqlist *L)
{
	int i;
	for(i=L->length/2;i>0;i--)
	        HeapAdjust(L,i,L->length);
		
	for(i=L->length;i>1;i--)
        {
		swap(L,1,i);//将堆顶记录和当前未经排序子序列的最后一个记录交换 
		HeapAdjust(L,1,i-1);//将1~i-1从新调整为大顶堆 
	}
}

从代码中可以看出,整个排序过程分为两个for循环。第一个for循环要完成的就是将现在的待排序序列构建成一个大顶堆。第二个for循环要完成的就是逐步将每个最大值的根结点与末尾元素交换,并且再调整其成为大顶堆。



实例分析

假设我们要排序的序列是{50,10,90,30,70,40,80,60,20} ,那么L.length=9,第一个for循环,代码第4行,i是从⌊9/2⌋=4开始,4→3→2→1的变量变化,即下图中的灰色结点,这里就利用了完全二叉树的性质。

堆与堆排序


其实将待排序的序列构建成为一个大顶堆,就是从下往左、从右到左,将每个非终端结点(非叶节点)当作根结点,将其和其子树调整成大顶堆4→3→2→1的变量变化其实也就是30,90,10,50的结点调整过程。

下面看下HeapAdjust的函数具体代码示例

void HeapAdjust(Sqlist *L,int s,int m)
{
	int temp,j;
	temp=L->r[s];
	for(j=2*s;j<=m;j*=2)//沿关键字较大的孩子结点向下筛选 
	{
		if(j<m&&L->r[j]<L->r[j+1])
			++j;.//j为关键字中较大的记录的下标 
		if(temp>=L->r[j])
			break;//结束循环 
		L->r[s]=L->r[j];
		s=j; 
	}
	L->r[s]=temp;//最后插入 
}


1.函数被第一次调用时,s=4,m=9,传入的SqList参数的值为length=9,r[10] ={0,50,10,90,30,70,40,80,60,20}。


2.第4行,将Lr[s]=L.r[4]=30赋值给temp,如下图

堆与堆排序


3.第5~13行,循环遍历其结点的孩子。这里,j变量为什么是从2*s开始呢?又为什么是j*=2递增呢?原因还是二叉树的性质,因为我们这棵是完全二叉树,当前结点序号是s,其左孩子的序号一定是2s,右孩子的序号一定是 2s+ 1,它们的孩子当然也是以2的位数序号增加,因此j变量才是这样循环。


4.第7~8行,此时j=2*4=8, j<m说明它不是最后一个结点,如果L.r[j]<L.r[j+1],则说明左孩子小于右孩子。我们的目的是要找到较大值,当然需要让j+1以便变成指向右孩子的下标。当前30的左右孩子是60和20,并不满足此条件,因此j还是8。


5.第9~10行,temp=30,L.r[j]=60,并不满足条件。


6.第11~12行,将60赋值给L.r[4],并令s=j=8。也就是说,当前算出,以30为根结点的子二叉树,当前最大值是60,在第8的位置。注意此时L.r[4]和L.r[8]的值均为60。


7. 再循环因为j=2*j=16,m=9,j>m,因此跳出循环。


8. 第14行,将temp=30赋值给L.r[s]=L.r[8],完成30与60的交换工作。如下图所示,本次函数调用完成。

堆与堆排序


9.再次调用HeapAdjust,此时s=3,m=9。第4行,temp=L.r[3]=90,第7~8行,由于40<80得到j+1=2*s+1=7。9~10行,由于90>80,因此退出循环,最终本次调用,整个序列未发什么改变。


10. 再次调用HeapAdjust,此时s=2,m=9。第4行,temp=L.r[2]=10,第7~8行,60<70,使得j=5。最终本次调用使得10与70进行了互换,如下图所示

堆与堆排序堆与堆排序


11.再次调用HeapAdjust,此时s=1,m=9。第4行,temp=L.r[1]=50,第7~8行,70<90,使得j=3。第11~12行,L.r[1]被赋值了90,并且s=3,再循环,由于2*j=6并未大于m,因此再次执行循环体,使得L.r[3]被赋值了80,完成循环后,L.[7]被赋值为50,最终本次调用使得50、90、80进行了轮换,如下图所示

堆与堆排序


        到此为止,构建大顶堆的过程完成了,也就是HeapSort函数的第4~5行循环执行完毕。
       


        接下来HeapSort函数的第6~11行就是正式的排序过程,由于有了前面的充分准备,其实这个排序就比较轻松了。下面是这部分代码示例

for(i=L->length;i>1;i--)
{ 
   swap(L,1,i);//将堆顶记录和当前未经排序子序列的最后一个记录交换 
   HeapAdjust(L,1,i-1); // 将L->r[1..i-1]重新调整为大顶堆 
}

1.当i=9时,第8行,交换20与90,第9行,将当前的根结点20进行大顶堆的调整,调整过程和刚才流程一样,找到它左右子结点的较大值,互换,再找到其子结点的较大值互换。此时序列变为{80,70,50,60,10,40,20,30,90},如下图

堆与堆排序

 

堆与堆排序
2.当i=8时,交换30与80,并将30与70交换,再与60交换,此时序列变为{70,60,50,30,10,40,20,80,90},如下图
堆与堆排序


堆与堆排序
3.后面的变化完全类似,过程如下图
 堆与堆排序
堆与堆排序

最终就得到一个完全有序的序列了。



堆排序复杂度分析

        它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
       

        在构建堆的过程中,因为是完全二叉树从最下层最右边的非终端结点开始构建,将它与其孩子进行比较和若有必要的互换,对于每个非终端结点来说,其实最多进行两次比较和互换操作,因此整个构建堆的时间复杂度为O(n)
       

        在正式排序时,第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离为⌊log2i⌋+1),并且需要取n-1次堆顶记录,因此,重建堆的时间复杂度为O(nlogn)
       

        所以总体来说,堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感,因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。
        空间复杂度上,它只有一个用来交换的暂存单元,也算是非常的不错。不过由于记录的比较与交换是跳跃式进行,因此堆排序也是一种不稳定的排序方法
        另外,由于初始构建堆所需的比较次数较多,因此,它并不适合待排序序列个数较少的情况