二叉樹的順序結(jié)構(gòu)

堆其實是具有一定規(guī)則限制的完全二叉樹。
普通的二叉樹是不太適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹會更適合使用順序結(jié)構(gòu)進行存儲。如下圖：

堆的概念及結(jié)構(gòu)

如果有一個關(guān)鍵碼的集合K={k0,k1,k2,...,kn?1}K=\{k_0, k_1, k_2, ..., k_{n-1}\}K={k0?,k1?,k2?,...,kn?1?}，當(dāng)把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并且滿足：$K_i\le K_{2?i+1}$且$K_i\le K_{2?i+2}$($K_i\ge K_{2?i+1}$且$K_i\ge K_{2?i+2}$)，i=0, 1, 2, …，則稱之為小堆(大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
堆的性質(zhì)：

• 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值
• 堆總是一棵完全二叉樹。
  

堆的實現(xiàn)

堆的創(chuàng)建

下面給出一個數(shù)組，這個數(shù)組邏輯上可以看做一棵完全二叉樹，但是還不滿足堆的條件?，F(xiàn)在我們可以通過算法，將它構(gòu)建成一個堆。

int a[] = {27,15,19,18,28,34,65,49,25,37};

要將其構(gòu)建成一個堆結(jié)構(gòu)，有兩種調(diào)整建堆的方法：一種是向上調(diào)整建堆，一種是向下調(diào)整建堆。

向上調(diào)整建堆

向上調(diào)整建堆主要是用于在堆數(shù)據(jù)結(jié)構(gòu)中，堆在插入數(shù)據(jù)后，為了繼續(xù)維持堆的結(jié)構(gòu)，所進行的一種調(diào)整。
大致調(diào)整過程如下：

經(jīng)過一次向上調(diào)整后，本來因為插入數(shù)據(jù)所導(dǎo)致的堆的結(jié)構(gòu)的破壞就被恢復(fù)了。
有了這個思路，可以將過程實現(xiàn)如下：

//a - 堆的順序存儲數(shù)組
//child - 需要進行向上調(diào)整的孩子下標(biāo)
void AdjustUp(HDataType* a, int child)
{assert(a != NULL);int parent = (child - 1) / 2;while (child > 0)//child為0時，child就到了堆頂，調(diào)整結(jié)束{//建小堆 - 孩子比雙親小，就互換位置if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//交換函數(shù)child = parent;parent = (child - 1) / 2;}else{break;}}
}

以上只是對一個數(shù)據(jù)進行的調(diào)整，要想實現(xiàn)堆的創(chuàng)建，需要將數(shù)組中的所有數(shù)據(jù)都進行一遍調(diào)整(堆頂元素除外)，所以可以更進一步，完成一棵完全二叉樹到堆的創(chuàng)建。

for (int i = 1; i < n; ++i)
{AdjustUp(a, i);
}

以上就是向上調(diào)整建堆的過程，我們可以分析一下它的時間復(fù)雜度。
因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化，使用滿二叉樹來證明。(時間復(fù)雜度看的本來就是近似值，多幾個節(jié)點并不影響最終結(jié)果)

假設(shè)樹的高度為h
第1層，$2^0$個節(jié)點，需要向上調(diào)整0層。
第2層，$2^1$個節(jié)點，需要向上調(diào)整1層。
第3層，$2^2$個節(jié)點，需要向上調(diào)整2層。
第4層，$2^3$個節(jié)點，需要向上調(diào)整3層。
…
第h-1層，$2^{h?2}$個節(jié)點，需要向上調(diào)整h-2層。
第h層，$2^{h?1}$個節(jié)點，需要向上調(diào)整h-1層。

則需要移動節(jié)點總的移動步數(shù)為：
$T(n)=2^0?0+2^1?1+2^2?2+2^3?3+......+2^{(h?2)}?(h?2)+2^{(h?1)}?(h?1)$
$2T(n)=2^1?0+2^2?1+2^3?2+2^4+3+......+2^{(h?1)}?(h?2)+2^h?(h?1)$

由錯位相減得：
$T(n)=?2^0?2^1?2^2?2^3?2^4?2^{(h?2)}?2^{(h?1)}+2^h?(h?1)$
$T(n)=2^h?(h?1)?(2^0+2^1+2^2+2^3+2^4+2^{(h?2)}+2^{(h?1)})$
$T(n)=2^h?(h?1)?(2^h?1)=2^h?(h?2)+1$
因為是滿二叉樹，所以節(jié)點數(shù)n與高度h之間存在如下關(guān)系：
$n=2^h?1$，$h=lo{g}_2(n+1)$
所以$T(n)=(n+1)?(lo{g}_2(n+1)?2)+1$
因此，得出向上建堆的時間復(fù)雜度是O($n?lo{g}_{2}n$)。

向下調(diào)整建堆

堆的刪除
向下調(diào)整建堆主要是用于在堆數(shù)據(jù)結(jié)構(gòu)中，堆在刪除數(shù)據(jù)后，為了繼續(xù)維持堆的結(jié)構(gòu)，所進行的一種調(diào)整。
這里要說明的是，堆的刪除是指刪除堆頂?shù)臄?shù)據(jù)。要刪除堆頂?shù)臄?shù)據(jù)并不是像順序表那樣覆蓋刪除。雖然堆的物理存儲結(jié)構(gòu)是順序結(jié)構(gòu)，但他邏輯上是樹形結(jié)構(gòu)，如果直接覆蓋刪除，本來是兄弟節(jié)點的變成父子節(jié)點，關(guān)系會完全打亂。并不能保證最終覆蓋刪除之后的結(jié)構(gòu)還是堆的結(jié)構(gòu)。
所以，堆的刪除有另一種巧妙的方法。先將堆頂?shù)臄?shù)據(jù)跟堆的最后一個數(shù)據(jù)進行交換，然后刪除堆的最后一個數(shù)據(jù)，就將堆頂數(shù)據(jù)刪除了。

但是，堆頂?shù)臄?shù)據(jù)刪除了，并沒有因此就萬事大吉。因為和堆頂數(shù)據(jù)進行交換的數(shù)據(jù)，現(xiàn)在處于堆頂位置，并不代表它就是堆中最小或最大的數(shù)據(jù)，堆的結(jié)構(gòu)可能通過交換后就此被破壞。所以，這里就要通過向下調(diào)整算法來恢復(fù)堆的結(jié)構(gòu)。
大致調(diào)整過程如下：

要注意的是：向下調(diào)整算法有一個前提，左右子樹必須都是堆，才能調(diào)整。
經(jīng)過一次向下調(diào)整后，本來因為刪除數(shù)據(jù)所導(dǎo)致的堆的結(jié)構(gòu)的破壞就被恢復(fù)了。
有了這個思路，可以將過程實現(xiàn)如下：

//a - 堆的順序存儲數(shù)組
//size - 堆的順序存儲數(shù)組的數(shù)據(jù)個數(shù)
//parent - 需要進行向下調(diào)整的雙親下標(biāo)
void AdjustDown(HDataType* a, int size, int parent)
{assert(a != NULL);//此時child代表左孩子int child = 2 * parent + 1;//孩子下標(biāo)在數(shù)組范圍內(nèi)進入循環(huán)while (child < size){//child+1代表右孩子//建小堆 - 右孩子存在的話，左右孩子誰更小，child存儲的就是誰的下標(biāo)變量if (child + 1 < size && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}

以上只是對一個數(shù)據(jù)進行的調(diào)整，要想實現(xiàn)堆的創(chuàng)建，這里我們從倒數(shù)第一個非葉子節(jié)點所形成的的子樹開始調(diào)整，一直調(diào)整到根節(jié)點的樹，就可以調(diào)整成堆。所以可以更進一步，完成一棵完全二叉樹到堆的創(chuàng)建。

//n-1是最后一個數(shù)據(jù)的下標(biāo)，((n-1)-1)/2是倒數(shù)第一個非葉子節(jié)點的下標(biāo)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{AdjustDown(a, n, i);
}

以上就是向下調(diào)整建堆的過程，我們可以分析一下它的時間復(fù)雜度。
同上，采取滿二叉樹的結(jié)構(gòu)來進行復(fù)雜度的計算。

假設(shè)樹的高度為h
第1層，$2^0$個節(jié)點，需要向下調(diào)整h-1層。
第2層，$2^1$個節(jié)點，需要向下調(diào)整h-2層。
第3層，$2^2$個節(jié)點，需要向下調(diào)整h-3層。
第4層，$2^3$個節(jié)點，需要向下調(diào)整h-4層。
…
第h-1層，$2^{h?2}$個節(jié)點，需要向下調(diào)整1層。
第h層，$2^{h?1}$個節(jié)點，需要向下調(diào)整0層。

則需要移動節(jié)點總的移動步數(shù)為：
$T(n)=2^0?(h?1)+2^1?(h?2)+2^2?(h?3)+2^3?(h?4)+......+2^{(h?2)}?1+2^{(h?1)}?0$
$2T(n)=2^1?(h?1)+2^2?(h?2)+2^2?(h?3)+2^4?(h?4)+......+2^{(h?1)}?1+2^h?0$

由錯位相減得：
$T(n)=(1?h)+2^1+2^2+2^3+2^4+2^{(h?2)}+2^{(h?1)}$
$T(n)=2^0+2^1+2^2+2^3+2^4+2^{(h?2)}+2^{(h?1)}?h$
$T(n)=2^h?1?h$
因為是滿二叉樹，所以節(jié)點數(shù)n與高度h之間存在如下關(guān)系：
$n=2^h?1$，$h=lo{g}_2(n+1)$
所以$T(n)=n?lon{g}_2(n+1)$
因此，得出向下建堆的時間復(fù)雜度是O(n)。
通過比較，向上建堆的時間復(fù)雜度是O($n?lo{g}_{2}n$)，向下建堆的時間復(fù)雜度是O(n)，所以采取向下建堆會更優(yōu)一些。
以上過程都是對小堆的建立，如果要建大堆，只需要將判斷條件略作更改即可：

//建小堆
if (a[child] < a[parent])
if (child + 1 < size && a[child + 1] < a[child])
if (a[child] < a[parent])//建大堆：
if (a[child] > a[parent])
if (child + 1 < size && a[child + 1] > a[child])
if (a[child] > a[parent])

堆的操作鏈接

最后，對于堆的各種操作需求，可以參考阿順的這篇堆(C語言實現(xiàn))