堆与堆排序课件

堆与堆排序软件学院王建文1-☞一、堆和堆排序的概念二、堆的调整三、建堆四、堆排序7.5.2堆和堆排序2-堆的定义：若n个元素的序列{a1a2…an}满足ai≤a2i或ai≥a2iai≤a2i+1ai≥a2i+1则分别称该序列{a1a2…an}为小根堆和大根堆。从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点3-例:下面序列为堆，对应的完全二叉树分别为:

7735625514354814483562559835774-堆的应用------优先级队列服务排队------见课本200,例5.1堆排序5-堆排序

若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）……如此反复，便能得到一个有序序列，这个过程称之为堆排序。

6-

实现堆排序需解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素后，调整剩余元素为一个新的堆？

下面先讨论第二个问题：7-一、堆和堆排序的概念

☞二、堆的调整三、建堆四、堆排序7.5.2堆和堆排序8-如何在输出堆顶元素后，调整剩余元素为一个新的堆？

解决方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”9-133827497665499713输出根并以最后一个元素代替之；比较其左右孩子值的大小，并与其中较小者交换；9727974997小根堆10-堆调整与数组变化的关系加入元素时向上调整删除元素时向下调整11-加入元素Fig.27-2Thestepsinadding85tothemaxheapofFigure27-1a12-AddinganEntryBeginatnextavailablepositionforaleafFollowpathfromthisleaftowardrootuntilfindcorrectpositionfornewentryAsthisisdoneMoveentriesfromparenttochildMakesroomfornewentry13-AddinganEntryFig.27-3ArevisionofstepsshowninFig.27-2toavoidswaps.14-AddinganEntryFig.27-4AnarrayrepresentationofthestepsinFig.27-3…continued→15-AddinganEntryFig.27-4(ctd.)AnarrayrepresentationofthestepsinFig.27-3.16-AddinganEntry----代码见课本203AlgorithmforaddingnewentrytoaheapAlgorithmadd(newEntry)

if(thearrayheapisfull)

Doublethesizeofthearray

newIndex=indexofnextavailablearraylocation

parentIndex=newIndex/2//indexofparentofavailablelocation

while(newEntry>heap[parentIndex])

{ heap[newIndex]=heap[parentIndex]

//moveparenttoavailablelocation

//updateindices

newIndex=parentIndex

parentIndex=newIndex/2

}//endwhile17-删除元素Fig.27-5ThestepstoremovetheentryintherootofthemaxheapofFig.27-3d18-RemovingtheRootFig.27-6Thestepsthattransformasemiheapintoaheapwithoutswaps.19-你能画出删除堆顶元素时相应数组的变化吗？删除元素代码见课本20420-一、堆和堆排序的概念二、堆的调整

☞三、建堆四、堆排序7.5.2堆和堆排序21-第一种方法： 把一个数组看成两部分，左边是堆，右边是还没加入堆的元素，步骤如下： 1、数组里的第一个元素自然地是一个堆 2、然后从第二个元素开始，一个个地加入左边的堆，当然，每加入一个元素就破坏了左边元素堆的性质，得重新把它调整为堆22-创建堆23-时间复杂度该方法创建堆的时间复杂度为O(nlogn)24-可以看出：

对一个无序序列反复“筛选”就可以得到一个堆即：从一个无序序列建堆的过程就是一个反复“筛选”的过程。那么：怎样判断一个序列是一个堆？或者说，建堆操作从哪儿着手？第二种方法：自底向上创建堆25-显然：单结点的二叉树是堆；在完全二叉树中所有以叶子结点（序号i>n/2）为根的子树是堆。这样，我们只需依次将以序号为n/2，n/2－1，……,1的结点为根的子树均调整为堆即可。

即：对应由n个元素组成的无序序列，“筛选”只需从第n/2个元素开始。26-由于堆实质上是一个完全二叉树，那么我们可以顺序存储一个堆。下面以一个实例介绍建一个小根堆的过程。例：有关键字为49，38，65，97，76，13，27，49的一组记录，将其按关键字调整为一个小根堆。493865977613274927-4938659776132749首先，调整从第n/2个元素开始将以该元素为根的二叉树调整为堆然后，将以序号为n/2－1的结点为根的二叉树调整为堆；再将以序号为n/2－2的结点为根的二叉树调整为堆；再将以序号为n/2－3的结点为根的二叉树调整为堆；49659776134938012345678279749974965136513494913132749274928-筛选过程的算法描述为：sift(rectypeR[],inti,intm)

//在数组R中将下标从i到m的元素序列调整为堆，即将以R[i]为根的子树调整为堆；初次调整的是以序号m/2的结点为根的子树；{intj;j=2*i;while(j<=m)//若j<=m，R[2*i]是R[i]的左孩子

{if(j<m&&R[j].key>R[j+1].key)j++;//比较左右孩子的大小，使j为较小的孩子的下标

29-if(R[i].key>R[j].key){R[i]<－>R[j];//将较小的孩子与根交换i=j;j=2*i;//上述交换可能使以该孩子结点为根的子树不再为堆，则需重新调整

}elsebreak;}}

30-将初始无序的R[1]到R[n]建成一个小根堆，可用以下语句实现：for(i=n/2;i>=1;i--)sift(R,i,n);31-自底向上地创建堆15161247620232515165124117627202332-Example(contd.)251516512411962720231525164125691123202733-Example(contd.)7152516412586911232027415251651276891123202734-Example(end)41525165127106891123202751525167121046891123202735-AnalysisWevisualizetheworst-casetimeofadownheapwithaproxypaththatgoesfirstrightandthenrepeatedlygoesleftuntilthebottomoftheheap(thispathmaydifferfromtheactualdownheappath)Sinceeachnodeistraversedbyatmosttwoproxypaths,thetotalnumberofnodesoftheproxypathsisO(n)

Thus,bottom-upheapconstructionrunsinO(n)timeBottom-upheapconstructionisfasterthannsuccessiveinsertionsandspeedsupthefirstphaseofheap-sort36-时间复杂度分析该方法创建堆的时间复杂度为O(n)证明过程请看教材341页37-一、堆和堆排序的概念二、堆的调整三、建堆

☞四、堆排序7.5.2堆和堆排序38-HeapsortFig.27-9Atraceofheapsort(a–c)39-HeapsortFig.27-9Atraceofheapsort(d–f)40-HeapsortFig.27-9Atraceofheapsort(g–i)41-HeapsortFig.27-9Atraceofheapsort(j–l)42-由以上分析知：若对一个无序序列建堆，然后输出根；重复该过程就可以由一个无需序列输出有序序列。实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。43-堆排序算法如下：HeapSort(rectypeR[])//对R[1]到R[n]进行堆排序{inti;rectypetemp;for(i=n/2;i>=1;i--)sift(R,i,n);//建初始堆for(i=n;i>1;i--)//进行n－1趟排序{temp=R[1];R[1]=R[i];R[i]=temp;

//根与最后一个元素交换

sift(R,1,i-1)//对R[1]到R[i-1]重新建堆

}}44-

堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。另外，堆排序仅需一个记录大小供交换用的辅助存储空间。

然而堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。45-Heaps