数据结构_课件_堆与堆排序

《数据结构_课件_堆与堆排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）……如此反复，便能得到一个有序序列，这个过程称之为堆排序。实现堆排序需解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素后，调整剩余元素为一个新的堆？下面先讨论第二个问题：一、堆和堆排序的概念☞二、堆的调整三、建堆四、堆排序7.5.2堆和堆排序如何在输出堆顶元素后，调整剩余元素为一个新的堆？解决方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这

3、个从堆顶至叶子的调整过程为“筛选”133827497665499713输出根并以最后一个元素代替之；比较其左右孩子值的大小，并与其中较小者交换；9727974997小根堆堆调整与数组变化的关系加入元素时向上调整删除元素时向下调整加入元素Fig.27-2Thestepsinadding85tothemaxheapofFigure27-1aAddinganEntryBeginatnextavailablepositionforaleafFollowpathfromthisleaftowardrootuntilfindcorrectpositionfornewen

4、tryAsthisisdoneMoveentriesfromparenttochildMakesroomfornewentryAddinganEntryFig.27-3ArevisionofstepsshowninFig.27-2toavoidswaps.AddinganEntryFig.27-4AnarrayrepresentationofthestepsinFig.27-3…continued→AddinganEntryFig.27-4(ctd.)AnarrayrepresentationofthestepsinFig.27-3.AddinganEntr

5、y----代码见课本203AlgorithmforaddingnewentrytoaheapAlgorithmadd(newEntry)if(thearrayheapisfull)DoublethesizeofthearraynewIndex=indexofnextavailablearraylocationparentIndex=newIndex/2//indexofparentofavailablelocationwhile(newEntry>heap[parentIndex]){heap[newIndex]=heap[parentIndex]//

6、moveparenttoavailablelocation//updateindicesnewIndex=parentIndexparentIndex=newIndex/2}//endwhile删除元素Fig.27-5ThestepstoremovetheentryintherootofthemaxheapofFig.27-3dRemovingtheRootFig.27-6Thestepsthattransformasemiheapintoaheapwithoutswaps.你能画出删除堆顶元素时相应数组的变化吗？删除元素代码见课本204一、堆和堆排序的

7、概念二、堆的调整☞三、建堆四、堆排序7.5.2堆和堆排序第一种方法：把一个数组看成两部分，左边是堆，右边是还没加入堆的元素，步骤如下：1、数组里的第一个元素自然地是一个堆2、然后从第二个元素开始，一个个地加入左边的堆，当然，每加入一个元素就破坏了左边元素堆的性质，得重新把它调整为堆创建堆时间复杂度该方法创建堆的时间复杂度为O(nlogn)可以看出：对一个无序序列反复“筛选”就可以得到一个堆即：从一个无序序列建堆的过程就是一个反复“筛选”的过程。那么：怎样判断一个序列是一个堆？或者说，建堆操作从哪儿着手？第二种方法：自底向上创建堆显然：单结点的二叉树是堆；在完

8、全二叉树中所有以叶子结点（序号i>n/2）为根的子树