第C語言數(shù)據(jù)結(jié)構(gòu)二叉樹之堆的實現(xiàn)和堆排序詳解目錄一、本章重點二、堆2.1堆的介紹2.2堆的接口實現(xiàn)三、堆排序

一、本章重點

堆的介紹堆的接口實現(xiàn)堆排序

二、堆

2.1堆的介紹

一般來說，堆在物理結(jié)構(gòu)上是連續(xù)的數(shù)組結(jié)構(gòu)，在邏輯結(jié)構(gòu)上是一顆完全二叉樹。

但要滿足

每個父親節(jié)點的值都得大于孩子節(jié)點的值，這樣的堆稱為大堆。每個父親節(jié)點的值都得小于孩子節(jié)點的值，這樣的堆稱為小堆。

那么以下就是一個小堆。

百度百科：

堆的定義如下：n個元素的序列{k1,k2,ki,,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時，稱之為堆。

若將和此次序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作此序列的存儲結(jié)構(gòu)）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不大于（或不小于）其左、右孩子結(jié)點的值。由此，若序列{k1,k2,,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。

下面序列是堆的是()。

A．97，56，38，66，23，42，12//不是大堆也不是小堆，即不是堆。

B．23，86，48，3，35，39，42//不是大堆也不是小堆，即不是堆。

C．05，56，20，23，40，38，29//不是大堆也不是小堆，即不是堆。

D．05，23，16，68，94，72，71，73//是小堆

只有D是堆而且是小堆，因此答案選D。

D的邏輯結(jié)構(gòu)：

父親節(jié)點和孩子節(jié)點的數(shù)組下標(biāo)有以下關(guān)系：

left_child=(parent+1)*2right_child=(parent+2)*2parent=（child-1）/2（這里的child左孩子和右孩子都適用）

以上就不做證明了，不過我們可以驗證一下，以上圖D的邏輯結(jié)構(gòu)為例，16的parent下標(biāo)是2，72的下標(biāo)是5，71的下標(biāo)是6，滿足left_child=(parent+1)*2、right_child=(parent+2)*2、parent=（child-1）/2。

有序一定是堆，堆不一定有序。

同時堆頂?shù)臄?shù)組是整個數(shù)組最大的數(shù)或者整個數(shù)組最小的數(shù)。

2.2堆的接口實現(xiàn)

第一件事我們就是要創(chuàng)建堆，實際就是創(chuàng)建一個數(shù)組，這里用動態(tài)數(shù)組。

typedefintHPDataType;

typedefstructHeap

HPDataType*a;

size_tsize;

size_tcapacity;

}HP;

堆創(chuàng)建好之后，我們需要對它進(jìn)行初始化。

第一個接口：

voidHeapInit(HP*php);

輕車熟路，將堆中的a置為NULL，size和capacity置為0。

或者這里可以設(shè)置capacity不為0的初始值也是可以的。

參考代碼：

voidHeapInit(HP*php)

assert(php);

php-a=NULL;

php-size=php-capacity=0;

}

我們對堆進(jìn)行初始化之后，也要在最后銷毀堆。

第二個接口：

voidHeapDestroy(HP*php)

銷毀堆，即銷毀一個動態(tài)數(shù)組

參考代碼：

voidHeapDestroy(HP*php)

assert(php);

free(php-

php-a=NULL;

php-size=php-capacity=0;

}

現(xiàn)在我們可以考慮往堆中插入數(shù)據(jù)了，要求插入新元素之后還是堆。

第三個接口：

voidHeapPush(HP*php,HPDataTypex)

堆沒有要求在哪個位置插入新元素，可以在任意的位置插入新元素，但要保證插入新元素之后還是堆。

由于數(shù)組在頭部還是在中間位置的插入復(fù)雜度是O（N），并且插入后不一定是堆了。

因此我們考慮的是直接在數(shù)組尾部插入新元素，然后用一個函數(shù)去調(diào)整數(shù)組的順序使得它還是一個堆。

那么核心代碼就是這個調(diào)整算法。

先來看這一個堆，插入新元素后該如何進(jìn)行調(diào)整。

我們在數(shù)組的最后插入22，原堆是一個小堆，此時我們需要從下往上去調(diào)整各個父親節(jié)點，使得該堆還是一個小堆。

換句話說：我們只需要調(diào)整下面有彩色的節(jié)點順序。

交換過程：如果孩子節(jié)點小于父親節(jié)點，那么將它們交換，然后迭代。

如果孩子節(jié)點大于父親節(jié)點就跳出循環(huán)。

迭代過程：將父親節(jié)點的下標(biāo)賦值給孩子節(jié)點的下標(biāo)，然后重新計算父親節(jié)點的下標(biāo)，計算方法：parent=（child-1）/2。

參考代碼：

voidAdjustUp(HPDataType*a,size_tchild)

size_tparent=(child-1)/2;

while(child0)

//如果孩子小于父親，則交換

if(a[child]a[parent])

Swap(a[child],a[parent]);

child=parent;

parent=(child-1)/2;

//孩子大于父親，則結(jié)束調(diào)整

else

break;

}

voidHeapPush(HP*php,HPDataTypex)

assert(php);

//動態(tài)數(shù)組，空間不夠要擴容

if(php-size==php-capacity)

size_tnewCapacity=php-capacity==04:php-capacity*2;

HPDataType*tmp=realloc(php-a,sizeof(HPDataType)*newCapacity);

if(tmp==NULL)

printf("reallocfailed\n");

exit(-1);

php-a=tmp;

php-capacity=newCapacity;

//尾插數(shù)據(jù)

php-a[php-size]=x;

++php-size;

//向上調(diào)整，控制保持是一個小堆

AdjustUp(php-a,php-size-1);

}

上面是多個數(shù)據(jù)的插入，那么如果插入第一個數(shù)據(jù)，這個函數(shù)還能幫助我們把數(shù)據(jù)插入堆中嗎？

答案是肯定的。

既然有Push數(shù)據(jù)到堆，自然有從堆中刪除元素了。

這里的刪除不同于棧和隊列的刪除，這里指的是將堆頂?shù)臄?shù)據(jù)刪除，刪除之后堆還是一個堆。為什么只實現(xiàn)刪堆頂?shù)臄?shù)據(jù)，因為簡單實用，這個接口是為后面的堆排序做準(zhǔn)備的。

第四個接口：

voidHeapPop(HP*php)

思路比較簡單：將數(shù)組第一個元素刪除，然后保持它還是一個小堆。

怎么刪除第一個數(shù)據(jù)呢？

這里的考慮是將數(shù)組第一個元素和數(shù)組最后一個交換，交換之后尾刪掉最后一個元素，達(dá)成刪除第一個元素的效果，復(fù)雜度是O（N），這里可以提一下，這種頭刪的方式是改變了數(shù)組元素的相對順序的。

刪除之后我們要做調(diào)整，使得堆還是小堆。

那么怎么調(diào)整呢？

以下是一個小堆

頭刪之后

如何調(diào)整它，使得它還是一個小堆？

這里的思路是：向下調(diào)整算法，首先parent=73，然后選出它子節(jié)點最小的值，然后它們之間交換，交換之后，將子節(jié)點看作新的父親節(jié)點，繼續(xù)向下調(diào)整，直到父親節(jié)點的左孩子不存在。

參考代碼：

voidAdjustDown(HPDataType*a,size_tsize,size_troot)

size_tparent=root;

size_tchild=parent*2+1;

while(childsize)

//1、選出左右孩子中小的那個

if(child+1sizea[child+1]a[child])

++child;

//2、如果孩子小于父親，則交換，并繼續(xù)往下調(diào)整

if(a[child]a[parent])

Swap(a[child],a[parent]);

parent=child;

child=parent*2+1;

else

break;

}

這里需要注意的是，為什么循環(huán)的結(jié)束條件不是右孩子不存在呢？

因為右孩子不存在時，也可能要進(jìn)行交換。

比如：

還需要注意的是左孩子存在右孩子不一定存在

if(a[child+1]a[child])

++child;

}

直接這樣寫a[child+1]可能會越界，因此要加上child+1size，保證child+1=size-1。

參考代碼：

voidHeapPop(HP*php)

assert(php);

assert(php-size

//將數(shù)組第一個元素和最后一個元素交換然后刪除最后一個元素，達(dá)到頭刪的目的。

Swap(php-a[0],php-a[php-size-1]);

--php-size;

//向下調(diào)整算法

AdjustDown(php-a,php-size,0);

}

其他接口補充：

由于比較簡單，理解起來不費勁，因此這里直接給出。

參考代碼：

boolHeapEmpty(HP*php)//判斷堆是否為空

assert(php);

returnphp-size==0;

size_tHeapSize(HP*php)//堆的元素個數(shù)

assert(php);

returnphp-size;

HPDataTypeHeapTop(HP*php)//取堆頂數(shù)據(jù)

assert(php);

assert(php-size

returnphp-a[0];

}

三、堆排序

堆排序：利用堆頂節(jié)點是整個數(shù)組的最大值或者最小值的特點，可以達(dá)到排序的目的。

比如我們要將1、5、2、4、8、6、10排成升序

可以將這幾個元素依次入堆，使得這些數(shù)據(jù)變成小堆。

然后我們可以取堆的第一個元素，它是整個數(shù)組最小的元素，要排升序，那么我們就需要將它排在第一個位置，然后刪除堆頂元素，由于我們的刪除接口的作用是：刪除堆頂元素，并保持堆還是小堆，那么我們調(diào)用刪除接口之后，再取堆頂元素，將它排在第二個位置，依次繼續(xù)下去，我們就能將這些數(shù)據(jù)排成升序了。

參考代碼：

voidHeapSort(int*a,intsize)

HPhp;

HeapInit(hp);

//建小堆

for(inti=0;isize;++i)

HeapPush(hp,a[i]);

//不斷取堆頂元素進(jìn)行排序

size_tj=0;

while(!HeapEmpty(hp))

a[j]=HeapTop(hp);

j++;

HeapPop(hp);

//銷毀堆，防止內(nèi)存泄露

HeapDestroy(hp);

}

這里的堆排序的空間復(fù)雜度是O（N），因為在堆區(qū)開辟了一個N個元素大小的堆空間。

堆排序看起來挺復(fù)雜的，那么它的時間復(fù)雜度是什么呢？

建小堆：0（N）

HeapPop（）一次執(zhí)行的是：頭刪堆頂元素（O（1）），然后依次向下比較，比較的次數(shù)是高度次，因為是完全二叉樹，比較的時間復(fù)雜度是O（logN）。

因此執(zhí)行