堆和堆排序092312113林秋照

1、堆和堆排序主講人：林秋照堆的定義堆可以定義為一顆二叉樹(shù)，樹(shù)的節(jié)點(diǎn)中包含鍵（每個(gè)節(jié)點(diǎn)一個(gè)鍵），并且滿(mǎn)足兩個(gè)條件：1、樹(shù)的形狀要求這棵二叉樹(shù)是基本完備的（或者簡(jiǎn)稱(chēng)為完全二叉樹(shù)），這意味著，樹(shù)的每一層都是滿(mǎn)的，除了最后一層最右邊的元素有可能缺位。2、父母優(yōu)勢(shì)要求每一個(gè)節(jié)點(diǎn)的鍵都要大于或等于它的子女的鍵（對(duì)于任何葉子我們認(rèn)為這個(gè)條件都是自動(dòng)滿(mǎn)足的）。3rir2i r2i+1 1236276549817355403498例如:是堆14不4例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）堆序列是完全二叉樹(shù)，則堆序列是完全二叉樹(shù)，則堆頂元素（完全二叉堆頂元素（完

2、全二叉樹(shù)的根）必為序列中樹(shù)的根）必為序列中n個(gè)元素的最小值或最大個(gè)元素的最小值或最大值值如下圖，是一個(gè)堆和數(shù)組的相互關(guān)系：二叉堆一般分為兩種：最大堆和最小堆。兩種堆內(nèi)部的數(shù)據(jù)都要滿(mǎn)足自己的特點(diǎn)。比如最大堆的特點(diǎn)是，每個(gè)父節(jié)點(diǎn)的元素值都不小于其孩子結(jié)點(diǎn)（如果存在）的元素值，因此，最大堆的最大元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）最小堆的性質(zhì)與最大堆恰好相反。堆的重要特性1、只存在一棵N個(gè)節(jié)點(diǎn)的完全二叉樹(shù)。它的高度等于堆的根總是包含了堆得最大元素。3、堆的一個(gè)節(jié)點(diǎn)以及該節(jié)點(diǎn)的子孫也是一個(gè)堆。4、可以用數(shù)組來(lái)實(shí)現(xiàn)堆，方法是用從上向下、從左向右的方式來(lái)記錄堆的元素?？梢栽谶@種數(shù)組從1到N的位置上存放堆元素，留下H

3、0，要么讓它空著，要么在其中放一個(gè)限位器，它的值大于堆中的任何一個(gè)元素。堆的構(gòu)造堆的構(gòu)造主要有兩種方法。第一種是自底向上堆構(gòu)造。在初始化一棵包含N個(gè)節(jié)點(diǎn)的完全二叉樹(shù)時(shí)，我們就按照給定的順序來(lái)放置鍵；然后按照下面的方法對(duì)樹(shù)進(jìn)行“堆化”。從最后的父母節(jié)點(diǎn)開(kāi)始到根為止，該算法檢查這些節(jié)點(diǎn)的鍵是否滿(mǎn)足父母優(yōu)勢(shì)要求。如果該節(jié)點(diǎn)不滿(mǎn)足，該算法把節(jié)點(diǎn)的鍵K和它子女的最大鍵進(jìn)行交換，然后再檢查在新位置上，K是不是滿(mǎn)足父母優(yōu)勢(shì)要求。這個(gè)過(guò)程一直持續(xù)到，對(duì)K的父母優(yōu)勢(shì)要求滿(mǎn)足為止（最終它必須滿(mǎn)足，因?yàn)閷?duì)于每個(gè)葉子中的鍵來(lái)說(shuō)，這個(gè)條件是自動(dòng)滿(mǎn)足的）。對(duì)于以當(dāng)前父母節(jié)點(diǎn)為根的子樹(shù)，在完成它的“堆化”以后，該算法對(duì)于該

4、節(jié)點(diǎn)的直接前趨進(jìn)行同樣的操作。在對(duì)樹(shù)的根完成了這種操作以后，該算法就停止了。8建堆是一個(gè)從下往上進(jìn)行“篩選”的過(guò)程。40554973816436122798例如: 原始序列為（40,55,49,73,12,27,78,81,64,36）123681734998817355l左/右子樹(shù)都已經(jīng)調(diào)整為堆l最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。9849406436122799881497355641236274012輸出98（ 98 和 12 進(jìn)行互換）之后，它就不是堆了需要對(duì)它進(jìn)行“篩選”98128173641298比較比較大頂堆大頂堆調(diào)節(jié)過(guò)程：調(diào)節(jié)過(guò)程：大頂堆的排序結(jié)果是升序排序大頂堆的

5、排序結(jié)果是升序排序另一種算法（效率較低）通過(guò)把新的鍵連續(xù)插入預(yù)先構(gòu)造好的堆，來(lái)構(gòu)造一個(gè)新堆。首先，把一個(gè)包含鍵K的新節(jié)點(diǎn)附加在當(dāng)前堆得最后一個(gè)葉子后面。然后按照下面的方法把K篩選到他的適當(dāng)位置。拿K和它父母的鍵做比較：如果后者大于等于K，算法停止（該機(jī)=結(jié)構(gòu)已經(jīng)是一個(gè)堆了）；否則，交換這兩個(gè)鍵并把K和它的新父母做比較。這種交換一直持續(xù)到K不大于它的最后一個(gè)字母，或者是達(dá)到了樹(shù)的根為止（圖6.12是一個(gè)圖示）。在這個(gè)算法中，我們也可以把一個(gè)空節(jié)點(diǎn)向上篩選，直到達(dá)到合適的位置，才把K的值賦給它。11例：小頂堆13273849657650979727384965765013輸出：1327493897

6、65765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738769713輸出：13 27 38124965502738769713輸出：13 27 387665502738499713輸出：13 27 38 495065762738499713輸出：13 27 38 499765762738495013輸出：13 27 38 49 506597762738495013輸出：13 27 38 49 509765762738495013輸出：13 27 38 49 50 65137665972738495013輸出：

7、13 27 38 49 50 659765762738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38 49 50 65 76 97算法HEAPBOTTOMUP/用自底向上算法，從給定數(shù)組的元素中構(gòu)造一個(gè)堆/輸入：一個(gè)可排序元素的數(shù)組H.R1N/輸出：一個(gè)堆H.R1N VOID HEAPADJUST (HEAPTYPE &H, INT S, INT M) / 已知H.RS.M中記錄的關(guān)鍵字除H.RS.KEY之外均滿(mǎn)足堆的定義，本函數(shù)依據(jù) / 關(guān)鍵字的大小對(duì)H.RS進(jìn)行調(diào)整，使H.RS.M成為一個(gè)大頂堆(對(duì)其中記錄的關(guān)鍵字而

8、言) RC = H.RS; / 暫存根結(jié)點(diǎn)的記錄 FOR ( J=2*S; J=M; J*=2 ) / 沿KEY較大的孩子結(jié)點(diǎn)向下篩選 IF ( JM & H.RJ.KEY= H.RJ.KEY ) BREAK; / 不需要調(diào)整 H.RS = H.RJ; S = J; / 把大關(guān)鍵字記錄往上調(diào) H.RS = RC; / 回移篩選下來(lái)的記錄 / HEAPADJUST從堆中刪除最大的鍵第一步：根的鍵和堆的最后一個(gè)鍵K做交換。第二步：堆的規(guī)模減1。第三步：嚴(yán)格按照我們?cè)谧缘紫蛏隙褬?gòu)造算法中的做法，把K沿著樹(shù)向下篩選，來(lái)對(duì)這棵樹(shù)較小的樹(shù)進(jìn)行“堆化”。也就是說(shuō)，驗(yàn)證K是否滿(mǎn)足父母優(yōu)勢(shì)：如果它滿(mǎn)足，

9、我們就完成了；如果不滿(mǎn)足，K和它較大的子女做交換；然后重復(fù)這個(gè)操作，知道K在新位置中滿(mǎn)足了父母優(yōu)勢(shì)要求為止。刪除的效率取決于在交換和堆的規(guī)模減1后，樹(shù)的“堆化”所需的鍵值比較次數(shù)。既然它所需的鍵值比較次數(shù)不可能超過(guò)堆的高度的兩倍，刪除的時(shí)間效率也是屬于O（的。堆排序堆排序的過(guò)程對(duì)N個(gè)數(shù)據(jù)的原始無(wú)序序列建堆，輸出堆頂元素將剩下的N-1個(gè)元素調(diào)整為堆，輸出堆頂元素將剩下的N-2個(gè)元素調(diào)整為堆，輸出堆頂元素.剩下的最后一個(gè)元素，本身就是堆堆排序算法VOID HEAPSORT ( HEAPTYPE &H ) CREATEHEAP(H); /建立初始堆 H.R1H.RN; /堆頂元素與最后一個(gè)元

10、素交換 FOR(I=N-1; I1; I-) /連續(xù)進(jìn)行堆調(diào)節(jié)和交換 HEAPADJUST(H); H.R1H.RI; VOID HEAPSORT ( HEAPTYPE &H ) / 對(duì)順序表H進(jìn)行堆排序。 FOR ( I=H.LENGTH/2; I0; -I ) / 把H.R1.H.LENGTH建成大頂堆 HEAPADJUST ( H, I, H.LENGTH ); W=H.R1 ; H.R1= H.RH.LENGTH; H.RH.LENGTH=W; /交換堆頂和堆底的記錄 FOR ( I=H.LENGTH-1; I1; -I ) HEAPADJUST(H, 1, I); / 從根開(kāi)始調(diào)整，將H 重新調(diào)整為大頂堆 W=H.R1; H.R1=H.RI; H.RI=W; / 相互交換 堆排序的時(shí)