7.堆 (Heap)

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

例程

為將元素X插入堆中，找到空閑位置，建立一個空穴，若滿足堆序性(英文：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.\n" ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}

以上是插入到一個二叉堆的過程。

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

ElementType DeleteMin( PriorityQueue H ){ int i, Child; ElementType MinElement, LastElement; if( IsEmpty( H ) ) { printf( "Queue is empty.\n" ); 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)確描述，由有限條指令組成，這些指令能在有限時間內(nèi)執(zhí)行完畢并產(chǎn)生確定性的輸出。

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

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

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

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

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

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

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

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

時間復(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

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