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

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

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

6-

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

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

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

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

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

對一個無序序列反復(fù)“篩選”就可以得到一個堆即：從一個無序序列建堆的過程就是一個反復(fù)“篩選”的過程。那么：怎樣判斷一個序列是一個堆？或者說，建堆操作從哪兒著手？第二種方法：自底向上創(chuàng)建堆25-顯然：單結(jié)點(diǎn)的二叉樹是堆；在完全二叉樹中所有以葉子結(jié)點(diǎn)（序號i>n/2）為根的子樹是堆。這樣，我們只需依次將以序號為n/2，n/2－1，……,1的結(jié)點(diǎn)為根的子樹均調(diào)整為堆即可。

即：對應(yīng)由n個元素組成的無序序列，“篩選”只需從第n/2個元素開始。26-由于堆實(shí)質(zhì)上是一個完全二叉樹，那么我們可以順序存儲一個堆。下面以一個實(shí)例介紹建一個小根堆的過程。例：有關(guān)鍵字為49，38，65，97，76，13，27，49的一組記錄，將其按關(guān)鍵字調(diào)整為一個小根堆。493865977613274927-4938659776132749首先，調(diào)整從第n/2個元素開始將以該元素為根的二叉樹調(diào)整為堆然后，將以序號為n/2－1的結(jié)點(diǎn)為根的二叉樹調(diào)整為堆；再將以序號為n/2－2的結(jié)點(diǎn)為根的二叉樹調(diào)整為堆；再將以序號為n/2－3的結(jié)點(diǎn)為根的二叉樹調(diào)整為堆；49659776134938012345678279749974965136513494913132749274928-篩選過程的算法描述為：sift(rectypeR[],inti,intm)

//在數(shù)組R中將下標(biāo)從i到m的元素序列調(diào)整為堆，即將以R[i]為根的子樹調(diào)整為堆；初次調(diào)整的是以序號m/2的結(jié)點(diǎn)為根的子樹；{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為較小的孩子的下標(biāo)

29-if(R[i].key>R[j].key){R[i]<－>R[j];//將較小的孩子與根交換i=j;j=2*i;//上述交換可能使以該孩子結(jié)點(diǎn)為根的子樹不再為堆，則需重新調(diào)整

}elsebreak;}}

30-將初始無序的R[1]到R[n]建成一個小根堆，可用以下語句實(shí)現(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-時間復(fù)雜度分析該方法創(chuàng)建堆的時間復(fù)雜度為O(n)證明過程請看教材341頁37-一、堆和堆排序的概念二、堆的調(diào)整三、建堆

?四、堆排序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-由以上分析知：若對一個無序序列建堆，然后輸出根；重復(fù)該過程就可以由一個無需序列輸出有序序列。實(shí)質(zhì)上，堆排序就是利用完全二叉樹中父結(jié)點(diǎn)與孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來排序的。43-堆排序算法如下：HeapSort(rectypeR[])//對R[1]到R[n]進(jìn)行堆排序{inti;rectypetemp;for(i=n/2;i>=1;i--)sift(R,i,n);//建初始堆for(i=n;i>1;i--)//進(jìn)行n－1趟排序{temp=R[1];R[1]=R[i];R[i]=temp;

//根與最后一個元素交換

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

}}44-

堆排序的時間主要耗費(fèi)在建初始堆和調(diào)整建新堆時進(jìn)行的反復(fù)“篩選”上。

堆排序在最壞情況下，其時間復(fù)雜度也為O(nlog2n)，這是堆排序的最大優(yōu)點(diǎn)。另外，堆排序僅需一個記錄大小供交換用的輔助存儲空間。

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