数据结构_课件_堆与堆排序VIP免费

堆与堆排序软件学院王建文☞一、堆和堆排序的概念二、堆的调整三、建堆四、堆排序7.5.27.5.2堆和堆排序堆和堆排序堆的定义：堆的定义：若n个元素的序列{a1a2…an}满足ai≤a2i或ai≥a2iai≤a2i+1ai≥a2i+1则分别称该序列{a1a2…an}为小根堆小根堆和大根堆。大根堆。从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于二叉树中任一非叶子结点均小于((大于大于))它的孩子结点它的孩子结点例例::下面序列为堆，对应的完全二叉树分别为:98773562551435481448356255983577堆的应用------优先级队列服务排队------见课本200,例5.1堆排序堆排序堆排序若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）……如此反复，便能得到一个有序序列，这个过程称之为堆排序堆排序。实现堆排序需解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素后，调整剩余元素为一个新的堆？下面先讨论第二个问题：一、堆和堆排序的概念☞二、堆的调整三、建堆四、堆排序7.5.27.5.2堆和堆排序堆和堆排序如何在输出堆顶元素后，调整剩余元素为一个如何在输出堆顶元素后，调整剩余元素为一个新的堆？新的堆？解决方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”“筛选”133827497665499713输出根并以最后一个元素代替之；比较其左右孩子值的大小，并与其中较小者交换；9727974997小根堆堆调整与数组变化的关系加入元素时向上调整删除元素时向下调整加入元素Fig.27-2Thestepsinadding85tothemaxheapofFigure27-1aAddinganEntryBeginatnextavailablepositionforaleafFollowpathfromthisleaftowardrootuntilfindcorrectpositionfornewentryAsthisisdoneMoveentriesfromparenttochildMakesroomfornewentryAddinganEntryFig.27-3ArevisionofstepsshowninFig.27-2toavoidswaps.AddinganEntryFig.27-4AnarrayrepresentationofthestepsinFig.27-3…continued→AddinganEntryFig.27-4(ctd.)AnarrayrepresentationofthestepsinFig.27-3.AddinganEntry----代码见课本203AlgorithmforaddingnewentrytoaheapAlgorithmadd(newEntry)if(thearrayheapisfull)DoublethesizeofthearraynewIndex=indexofnextavailablearraylocationparentIndex=newIndex/2//indexofparentofavailablelocationwhile(newEntry>heap[parentIndex]){heap[newIndex]=heap[parentIndex]//moveparenttoavailablelocation//updateindicesnewIndex=parentIndexparentIndex=newIndex/2}//endwhile删除元素Fig.27-5ThestepstoremovetheentryintherootofthemaxheapofFig.27-3dRemovingtheRootFig.27-6Thestepsthattransformasemiheapintoaheapwithoutswaps.你能画出删除堆顶元素时相应数组的变化吗？删除元素代码见课本204一、堆和堆排序的概念二、堆的调整☞三、建堆四、堆排序7.5.27.5.2堆和堆排序堆和堆排序第一种方法：把一个数组看成两部分，左边是堆，右边是还没加入堆的元素，步骤如下：1、数组里的第一个元素自然地是一个堆2、然后从第二个元素开始，一个个地加入左边的堆，当然，每加入一个元素就破坏了左边元素堆的性质，得重新把它调整为堆创建堆时间复杂度该方法创建堆的时间复杂度为O(nlogn)可以看出：对一个无序序列反复“筛选”反复“筛选”就可以得到一个堆堆即：从一个无序序列建堆建堆的过程就是一个反复“筛选”反复“筛选”的过程的过程。那么：怎样判断一个序列是一个堆？或者说，建堆操作从哪儿着手？第二种方法：自底向上创建堆显然：单结点的二叉树是堆；在完全二叉树中所有以叶子结点（序号i>n/2）为根的子树是堆。这样，我们只需依次将以序号为n/2，n/2－1，……,1的结点为根的子树均调整为堆即可。即：对应由即：对应由nn个元素组成的无序序列，“筛选”只个元素组成的无序序列，“筛选”只需从第需从第n/2n/2...