堆與堆排序課件

堆與堆排序軟件學院王建文1-?一、堆和堆排序的概念二、堆的調整三、建堆四、堆排序7.5.2堆和堆排序2-堆的定義：若n個元素的序列{a1a2…an}滿足ai≤a2i或ai≥a2iai≤a2i+1ai≥a2i+1則分別稱該序列{a1a2…an}為小根堆和大根堆。從堆的定義可以看出，堆實質是滿足如下性質的完全二叉樹：二叉樹中任一非葉子結點均小于(大于)它的孩子結點3-例:下面序列為堆，對應的完全二叉樹分別為:

7735625514354814483562559835774-堆的應用------優(yōu)先級隊列服務排隊------見課本200,例5.1堆排序5-堆排序

若在輸出堆頂?shù)淖钚≈担ㄗ畲笾担┖?，使得剩余n-1個元素的序列重又建成一個堆，則得到n個元素的次小值（次大值）……如此反復，便能得到一個有序序列，這個過程稱之為堆排序。

6-

實現(xiàn)堆排序需解決兩個問題：1、如何由一個無序序列建成一個堆？2、如何在輸出堆頂元素后，調整剩余元素為一個新的堆？

下面先討論第二個問題：7-一、堆和堆排序的概念

?二、堆的調整三、建堆四、堆排序7.5.2堆和堆排序8-如何在輸出堆頂元素后，調整剩余元素為一個新的堆？

解決方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結點值與左、右子樹的根結點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結點，將得到新的堆，稱這個從堆頂至葉子的調整過程為“篩選”9-133827497665499713輸出根并以最后一個元素代替之；比較其左右孩子值的大小，并與其中較小者交換；9727974997小根堆10-堆調整與數(shù)組變化的關系加入元素時向上調整刪除元素時向下調整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-你能畫出刪除堆頂元素時相應數(shù)組的變化嗎？刪除元素代碼見課本20420-一、堆和堆排序的概念二、堆的調整

?三、建堆四、堆排序7.5.2堆和堆排序21-第一種方法： 把一個數(shù)組看成兩部分，左邊是堆，右邊是還沒加入堆的元素，步驟如下： 1、數(shù)組里的第一個元素自然地是一個堆 2、然后從第二個元素開始，一個個地加入左邊的堆，當然，每加入一個元素就破壞了左邊元素堆的性質，得重新把它調整為堆22-創(chuàng)建堆23-時間復雜度該方法創(chuàng)建堆的時間復雜度為O(nlogn)24-可以看出：

對一個無序序列反復“篩選”就可以得到一個堆即：從一個無序序列建堆的過程就是一個反復“篩選”的過程。那么：怎樣判斷一個序列是一個堆？或者說，建堆操作從哪兒著手？第二種方法：自底向上創(chuàng)建堆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)

//在數(shù)組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]建成一個小根堆，可用以下語句實現(xiàn)：for(i=n/2;i>=1;i--)sift(R,i,n);31-自底向上地創(chuàng)建堆15161247620232515165124117627202332-Example(contd.)251516512411962720231525164125691123202733-Example(contd.)7152516412586911232027415251651276891123202734-Example(end)41525165127106891123202751525167121046891123202735-AnalysisWevisualizetheworst-casetimeofadownheapwithaproxypaththatgoesfirstrightandthenrepeatedlygoesleftuntilthebottomoftheheap(thispathmaydifferfromtheactualdownheappath)Sinceeachnodeistraversedbyatmosttwoproxypaths,thetotalnumberofnodesoftheproxypathsisO(n)

Thus,bottom-upheapconstructionrunsinO(n)timeBottom-upheapconstructionisfasterthannsuccessiveinsertionsandspeedsupthefirstphaseofheap-sort36-時間復雜度分析該方法創(chuàng)建堆的時間復雜度為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)，這是堆排序的最大優(yōu)點。另外，堆排序僅需一個記錄大小供交換用的輔助存儲空間。

然而堆排序是一種不穩(wěn)定的排序方法，它不適用于待排序記錄個數(shù)n較少的情況，但對于n較大的文件還是很有效的。45-Heaps