7.堆 (Heap)

　　在計(jì)算機(jī)科學(xué)中，堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有一個(gè)值。通常我們所說的堆的數(shù)據(jù)結(jié)構(gòu)，是指二叉堆。堆的特點(diǎn)是根結(jié)點(diǎn)的值小(或大)，且根結(jié)點(diǎn)的兩個(gè)子樹也是一個(gè)堆。

　　例程

　　為將元素X插入堆中，找到空閑位置，建立一個(gè)空穴，若滿足堆序性(英文：heap order)，則插入完成;否則將父節(jié)點(diǎn)元素裝入空穴，刪除該父節(jié)點(diǎn)元素，完成空穴上移。直至滿足堆序性。這種策略叫做上濾(percolate up)。

　　void Insert( ElementType X, PriorityQueue H ){ int i; if( IsFull(H) ) { printf( "Queue is full. " ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}

　　以上是插入到一個(gè)二叉堆的過程。

　　DeleteMin，刪除小元，即二叉樹的根或父節(jié)點(diǎn)。刪除該節(jié)點(diǎn)元素后，隊(duì)列后一個(gè)元素必須移動到堆得某個(gè)位置，使得堆仍然滿足堆序性質(zhì)。這種向下替換元素的過程叫作下濾。

　　ElementType DeleteMin( PriorityQueue H ){ int i, Child; ElementType MinElement, LastElement; if( IsEmpty( H ) ) { printf( "Queue is empty. " ); return H->Elements[0]; } MinElement = H->Elements[1]; LastElement = H->Elements[H->Size--]; for( i = 1; i*2 <= H->Size; i = Child ) { /* Find smaller child. */ Child = i*2; if( Child != H->Size && H->Elements[Child+1] < H->Elements[Child] ) Child++; /* Percolate one level. */ if( LastElement > H->Elements[Child] ) H->Elements[i] = H->Elements[Child]; else break; } H->Elements[i] = LastElement; return MinElement;}

　　7.算法設(shè)計(jì)的分析技術(shù)

　　算法是對問題求解過程的準(zhǔn)確描述，由有限條指令組成，這些指令能在有限時(shí)間內(nèi)執(zhí)行完畢并產(chǎn)生確定性的輸出。

　　進(jìn)行算法的時(shí)間復(fù)雜度分析，就是求其T(n)，并用O、Ω或是Θ以盡可能簡單的形式進(jìn)行表示。

　　理想情況下，希望能夠使用Θ表示算法的時(shí)間復(fù)雜性。退而求其次，可以使用O或是Ω。

　　使用O時(shí)，希望估計(jì)的上界的階越小越好。

　　使用Ω時(shí)，希望估計(jì)的下界的階越大越好。

　　樹的高度為ëlognû,所以將一個(gè)元素插入大小為n的堆所需要的時(shí)間是O(logn).

　　delete(H,i) 所需要的時(shí)間是O(logn).

　　make-heap(A): 從數(shù)組A創(chuàng)建堆

　　方法1：從一個(gè)空堆開始，逐步插入A中的每個(gè)元素，直到A中所有元素都被轉(zhuǎn)移到堆中。

　　時(shí)間復(fù)雜度為O(nlogn).

　　方法2：

　　MAKEHEAP(創(chuàng)建堆)

　　輸入：數(shù)組A[1…n]

　　輸出：將A[1…n]轉(zhuǎn)換成堆

　　1. fori← ën/2û downto 1

　　2. Sift-down(A,i){使以A[i]為根節(jié)點(diǎn)的子樹調(diào)整成為堆，故調(diào)用down過程}

　　3. endfor

　　時(shí)間復(fù)雜度為O(n).