堆与堆排序
引言
在简单选择排序中,我们每一趟比较时并没有将比较的结果保存下来,这样下一趟可能会产生重复的比较,导致效率降低。
如果可以做到每次在选择到最小记录的同时,并根据比较结果对其他记录做出相应的调整,那样排序的总体效率就会非常高了。
下面要介绍的堆排序(Heapsort)就是对简单选择排序的一种改进,是由Floyd和Williams在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},如下图
最终就得到一个完全有序的序列了。
堆排序复杂度分析
它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
在构建堆的过程中,因为是完全二叉树从最下层最右边的非终端结点开始构建,将它与其孩子进行比较和若有必要的互换,对于每个非终端结点来说,其实最多进行两次比较和互换操作,因此整个构建堆的时间复杂度为O(n)。
在正式排序时,第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离为⌊log2i⌋+1),并且需要取n-1次堆顶记录,因此,重建堆的时间复杂度为O(nlogn)。
所以总体来说,堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感,因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。
空间复杂度上,它只有一个用来交换的暂存单元,也算是非常的不错。不过由于记录的比较与交换是跳跃式进行,因此堆排序也是一种不稳定的排序方法。
另外,由于初始构建堆所需的比较次数较多,因此,它并不适合待排序序列个数较少的情况。