第6章_堆排序_算法分析與設(shè)計(jì)_杭電_褚一平

1、6.1 堆 (二叉)堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對(duì)象，它可以被視為一顆完 全二叉樹，樹中每個(gè)節(jié)點(diǎn)和數(shù)組中存放該節(jié)點(diǎn)值的那個(gè)元 素對(duì)應(yīng)。如果表示堆的數(shù)組為A，那么樹的根為A1。 表示堆的數(shù)組A是一個(gè)具有兩個(gè)屬性的對(duì)象：length(A)是 數(shù)組中的元素個(gè)數(shù)，heap-size(A)是存放在A中的堆的元素 個(gè)數(shù)；Aheap-size(A)之后的元素都不屬于相應(yīng)的堆。也 就是：Heap-size(A) Ai 4 then largest l 5 else largest i 6 If r heap-sizeA and Ar Alargest 7 then largest r 8 If largest i 9

2、 then exchange AiAlargest 10 MAX-HEAPIFY(A, largest) 8 6.1 MAX-HEAPIFY過程 9 6.1 MAX-HEAPIFY過程 10 6.1 MAX-HEAPIFY過程 6.2 MAX-HEAPIFY時(shí)間 當(dāng)MAX-HEAPIFY作用在一棵以節(jié)點(diǎn)i為根的， 大小為n的子樹上時(shí)，其運(yùn)行時(shí)間為調(diào)整元素 Ai，ALEFT(i)和ARIGHT(i)的關(guān)系時(shí)所用時(shí) 間(1)，再加上對(duì)以i的某個(gè)子結(jié)點(diǎn)為根的子樹 遞歸調(diào)用MAX-HEAPIFY所需的時(shí)間。i結(jié)點(diǎn)的 子樹大小至多為2n/3，那么MAX-HEAPFY的運(yùn) 行時(shí)間為： T(n) T(2n/

3、3) + (1) 根據(jù)主定理，該遞歸式的解為T(n) (lgn) 6.3 建堆 我們可以自底向上的用MAX-HEAPIFY來將一個(gè) 數(shù)組A1.n變成一個(gè)最大堆。過程BUILD-MAX- HEAP對(duì)樹中的每一個(gè)其他節(jié)點(diǎn)都調(diào)用一次 MAX-HEAPIFY。 BUILD-MAX-HEAP(A) 1 heap-sizeA lengthA do MAX-HEAPIFY(A,i) 2 for i length A / 2 downto 1 13 建堆過程 14 建堆過程 15 建堆過程 16 建堆過程 17 建堆過程 18 建堆過程 BUILD-MAX-HEAP正確性 為了證明BUILD-MAX-HEAP

4、的正確性，我們使 用如下的循環(huán)不變式： 在第23行中for循環(huán)的每一次迭代開始時(shí)，節(jié) 點(diǎn)i+1，i+2， n都是一個(gè)最大堆的根。 我們需要證明在第一次循環(huán)迭代之前，這個(gè)不 變式已為真。每次循環(huán)迭代都能保持此不變 式，并且在循環(huán)結(jié)束時(shí)這個(gè)不變式會(huì)提供一個(gè) 很有用的屬性來顯示程序的正確性。 BUILD-MAX-HEAP正確性 也是平凡最大堆的根。 保持：要證明每次迭代都保持了循環(huán)不變式， 注意到結(jié)點(diǎn)i的子結(jié)點(diǎn)的編號(hào)均比i大，于是，根 據(jù)循環(huán)不變式，這些子結(jié)點(diǎn)都是最大堆的根。 這也是調(diào)用函數(shù)MAX-HEAPIFY(A,i)，以使結(jié)點(diǎn) i成為最大堆的根的前提條件。此外，MAX- HEAPFY的調(diào)用保持

5、了結(jié)點(diǎn)i+1,i+2,n為最大 堆的性質(zhì)。 在for循環(huán)中遞減i，即為下一次迭代重新建立了 循環(huán)不等式。 初始化：在第一輪循環(huán)迭代之前，i n / 2 。 結(jié)點(diǎn) n / 2 1，n / 2 2 ，n都是葉結(jié)點(diǎn)， BUILD-MAX-HEAP正確性 終止：過程終止時(shí)，i=0.根據(jù)循環(huán)不等式，我們 知道結(jié)點(diǎn)1，2，n中，每個(gè)都是最大堆的 根，特別的，結(jié)點(diǎn)1就是一個(gè)最大堆的根。 我們可以這樣來計(jì)算BUILD-MAX-HEAP運(yùn)行時(shí) 間的一個(gè)簡(jiǎn)單上界：每次調(diào)用MAX-HEAPFY的 時(shí)間為O(lgn)，共有O(n)次調(diào)用，故運(yùn)行時(shí)間為 O(nlgn)。這個(gè)界盡管是對(duì)的，但是從漸近意義 上講不夠緊確。

6、h 2 O n O ( h ) O n 2 O n hh O ( n ) 2 BUILD-MAX-HEAP精確上界 MAX-HEAPIFY作用在高度為h的結(jié)點(diǎn)上的時(shí)間 為O(h)，我們可以將BUILD-MAX-HEAP的代價(jià) 表達(dá)為上確界 將x=1/2代入幾何級(jí)數(shù)的微分來計(jì)算(A.8)，則 于是，BUILD-MAX-HEAP的運(yùn)行時(shí)間的界為： h lg n h 0 lg n h 0 2 n h 1 2 2 1 / 2 (1 1 / 2 ) h 0 h h h h h 0 2 lg n h 0 6.4 堆排序算法 開始時(shí)，堆排序算法先后用BUILD-MAX-HEAP 將輸入數(shù)組A1.n構(gòu)造成一個(gè)

7、最大堆，因?yàn)閿?shù) 組中最大元素在A1，可以通過把它與An互換 來達(dá)到最終正確的位置。 接下來，如果從堆中去掉結(jié)點(diǎn)n，可以很容易地 將A1.n-1建成最大堆。原來根的子女仍是最大 堆，而新的根元素可能違背了最大堆性質(zhì)。這 時(shí)調(diào)用MAX-HEAPIFY(A,1)就可以保持這一性 質(zhì)，在A1.(n-1)中構(gòu)建出最大堆。 6.4 堆排序算法 HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 for i lengthA downto 2 3 do exchange A1Ai 4 heap-sizeAheap-sizeA-1 5 MAX-HEAPIFY(A,1) HEAPSORT過程的時(shí)間

8、代價(jià)為O(nlgn)，其中 調(diào)用BUILD-MAX-HEAP的時(shí)間為O(n)，n次 MAX-HEAPIFY調(diào)用中每一次的時(shí)間代價(jià)為 O(lgn)。 6.4 優(yōu)先級(jí)隊(duì)列 堆排序的應(yīng)用：（最大/最小）優(yōu)先級(jí)隊(duì)列 作業(yè)調(diào)度：找出優(yōu)先級(jí)最高的、插入作業(yè)、調(diào)整優(yōu)先級(jí) 優(yōu)先級(jí)隊(duì)列是一種用來維護(hù)由一組元素構(gòu)成的集合 S的數(shù)據(jù)結(jié)構(gòu)，這一組元素中的每一個(gè)都有一個(gè)關(guān) 鍵字key。一個(gè)最大優(yōu)先級(jí)隊(duì)列支持以下操作： INSERT(S,x)：把元素x插入集合S MAXIMUM(S)：返回S中具有最大關(guān)鍵字的元素 EXTRACT-MAX(S)：去掉并返回S中的具有最大關(guān)鍵字的 元素 INCREASE-KEY(S,x,k)

9、：將元素x的關(guān)鍵字的值增 加到k，這里k值不能小于x的原關(guān)鍵字的值。 優(yōu)先級(jí)隊(duì)列的操作 程序HEAP-MAXIMUM用(1)時(shí)間實(shí)現(xiàn)了MAXIMUM HEAP-MAXIMUM(A) return A1 程序HEAP-EXTRACT-MAX實(shí)現(xiàn)了EXTRACT-MAX HEAP-EXTRACT-MAX(A) if heap-sizeA1 then error ”heap underflow” maxA1 A1Aheap-sizeA heap-sizeAheap-sizeA 1 MAX-HEAPIFY(A,1) return max 27 優(yōu)先級(jí)隊(duì)列的操作 程序HEAP-INCREASE-KEY實(shí)現(xiàn)了INCREASE-KEY操作。在優(yōu)先 級(jí)隊(duì)列中關(guān)鍵字值需要增加的元素由對(duì)應(yīng)數(shù)組的下標(biāo)i來標(biāo)識(shí)。該過 程首先將元素Ai的關(guān)鍵字值更新為新的值。由于增大Ai的關(guān)鍵字 可能會(huì)違反最大堆性質(zhì)，因此在從本結(jié)點(diǎn)往根移動(dòng)的路徑上，為新 增大的關(guān)鍵字尋找合適的位置。在移動(dòng)的過程中，此元素不斷地和 其父母相比，如果此元素的關(guān)鍵字較大，則交換他們的關(guān)鍵字且繼 續(xù)移動(dòng)。當(dāng)元素的關(guān)鍵字小于其父母時(shí)，最大堆性質(zhì)成立，程序終 止 HEAP-INCREASE-KEY(A,i,key) 1 if key 1 and APARENT(i)Ai 5 do exchange AiAPARENT