C語(yǔ)言堆與二叉樹(shù)的順序結(jié)構(gòu)與實(shí)現(xiàn)

第C語(yǔ)言堆與二叉樹(shù)的順序結(jié)構(gòu)與實(shí)現(xiàn)目錄一.二叉樹(shù)的順序結(jié)構(gòu)二.堆的概念及結(jié)構(gòu)三.堆的實(shí)現(xiàn)四.堆排序(具有缺陷型)

一.二叉樹(shù)的順序結(jié)構(gòu)

普通的二叉樹(shù)是不適合用數(shù)組來(lái)存儲(chǔ)的，因?yàn)榭赡軙?huì)存在大量的空間浪費(fèi)。而完全二叉樹(shù)更適合使用順序結(jié)構(gòu)存儲(chǔ)?，F(xiàn)實(shí)中我們通常把堆(一種二叉樹(shù))使用順序結(jié)構(gòu)的數(shù)組來(lái)存儲(chǔ)，需要注意的是這里的堆和操作系統(tǒng)虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

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

如果有一個(gè)關(guān)鍵碼的集合K={，，，，}，把它的所有元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿(mǎn)足：=且=)i=0，1，2，則稱(chēng)為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：

堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值堆總是一棵完全二叉樹(shù)

三.堆的實(shí)現(xiàn)

將要實(shí)現(xiàn)的接口及堆的創(chuàng)建：

（由于堆的特點(diǎn)，這里使用數(shù)組結(jié)構(gòu)實(shí)現(xiàn)）

//將要實(shí)現(xiàn)的是大堆

typedefintHPDataType;

//創(chuàng)建堆結(jié)構(gòu)體

typedefstructHeap

HPDataType*arr;//數(shù)組存儲(chǔ)

size_tcapacity;//容量

size_tsize;//堆里的元素個(gè)數(shù)

//初始化堆

voidHeapInit(HP*php);

//銷(xiāo)毀堆

voidHeapDestroy(HP*php);

voidswap(HPDataType*pa,HPDataType*pb);

//插入堆，后面插入

voidHeapPush(HP*php,HPDataTypex);

//刪除堆元素，第一個(gè)元素

voidHeapPop(HP*php);

boolHeapEmpty(HP*php);

//堆的大小

size_tHeapSize(HP*php);

//返回堆頂元素

HPDataTypeHeapTop(HP*php);

堆的初始化

voidHeapInit(HP*php)

assert(php);//堆必須存在

php-arr=NULL;

php-capacity=php-size=0;

}

堆的銷(xiāo)毀

voidHeapDestroy(HP*php)

assert(php);

//銷(xiāo)毀數(shù)組

free(php-arr);

php-arr=NULL;

php-capacity=php-size=0;

}

交換函數(shù)

voidswap(HPDataType*pa,HPDataType*pb)

HPDataTypetemp=*pa;

*pa=*pb;

*pb=temp;

}

堆的插入

這里的插入是在堆的最后面插入，堆不能任意位置插入會(huì)破壞堆的結(jié)構(gòu)，這里最后面插入也會(huì)面臨一個(gè)問(wèn)題，插入必須還是大堆，那就要使用向上調(diào)整法

接下來(lái)插入一個(gè)70，由于70最大，所以會(huì)使用到向上調(diào)整法，如下圖：

將新插入進(jìn)來(lái)的元素與父節(jié)點(diǎn)對(duì)比，如果父節(jié)點(diǎn)小于子節(jié)點(diǎn)，就交換，依次往下進(jìn)行，否則就不用交換，終止向上調(diào)整

//向上調(diào)整法

voidAdjustUp(HPDataType*arr,size_tchild)

//父節(jié)點(diǎn)

HPDataTypeparent=(child-1)/2;

//交換

while(child0)//用child控制，parent會(huì)死循環(huán)

//如果父節(jié)點(diǎn)更大，說(shuō)明需要更換

if(arr[parent]arr[child])

swap(arr[parent],arr[child]);

//孩子和父親都往上走

child=parent;

parent=(child-1)/2;

voidHeapPush(HP*php,HPDataTypex)

assert(php);

//擴(kuò)容

if(php-size==php-capacity)

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

HPDataType*temp=(HPDataType*)realloc(php-arr,sizeof(HPDataType)*newcapacity);

assert(temp);

php-arr=temp;

php-capacity=newcapacity;

php-arr[php-size]=x;

++php-size;

//需要將孩子穿過(guò)去，注意size是在最后一個(gè)位置的后一個(gè)位置

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

}

堆的刪除

堆的刪除刪除的是堆頂?shù)脑兀遣荒苊つ康膶⒌谝粋€(gè)元素刪除，然后將后面的元素往前覆蓋，因?yàn)楫?dāng)數(shù)組里的元素沒(méi)有順序時(shí)，就會(huì)破壞了堆的結(jié)構(gòu)，所以這里需要用到向下調(diào)整算法

在插入的基礎(chǔ)上，刪除掉堆頂?shù)臄?shù)，也就是70，此時(shí)就要使用到向下調(diào)整法，如下圖：

因?yàn)槲覀儎h除的是堆頂?shù)脑?，所以可以這樣

先將堆頂元素和最后一個(gè)元素進(jìn)行交換，再刪除交換后的堆尾的元素，此時(shí)的堆頂元素因?yàn)椴恢来笮。詫⑵浜妥约旱膬蓚€(gè)孩子中最大的比較，如果堆頂?shù)脑匦【徒粨Q，依次往下進(jìn)行，否則就不交換，結(jié)束向下調(diào)整

voidAdjustDown(HPDataType*arr,size_tparent,size_tsize)

//假設(shè)左孩子最小

HPDataTypechild=(parent*2)+1;

//使用child控制，parent會(huì)越界

while(childsize)

//如果右孩子更小則讓右孩子去比較，注意右孩子是否存在

if(arr[child]arr[child+1]child+1size)

++child;

//將父親和孩子比較，父親更大則交換

if(arr[parent]arr[child])

swap(arr[parent],arr[child]);

parent=child;

child=(parent*2)-1;

//當(dāng)出現(xiàn)父親小于孩子時(shí)，說(shuō)明不用往下遍歷了

else

break;

voidHeapPop(HP*php)

assert(php);

//堆不能為空

assert(php-size

//首尾元素的交換

HPDataTypetemp=php-arr[0];

php-arr[0]=php-arr[php-size-1];

php-arr[php-size-1]=temp;

//刪除交換后的尾元素

--php-size;

//向下調(diào)整

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

}

判空堆是否為空

boolHeapEmpty(HP*php)

assert(php);

returnphp-size==0;

}

返回堆的大小

size_tHeapSize(HP*php)

assert(php);

returnphp-size;

}

返回堆頂元素

HPDataTypeHeapTop(HP*php)

assert(php);

//得要有元素

assert(php-size

returnphp-arr[0];

}

四.堆排序(具有缺陷型)

利用以上接口實(shí)現(xiàn)堆排序（具有缺陷），具有O(n)的空間復(fù)雜度

intmain()

intarr[]={2,5,6,4,54,23,1,45,67,98};

intsize=sizeof(arr)/sizeof(arr[0];

HPhp;//創(chuàng)建堆

HeapInit(hp);//初始化

//堆插入元素，時(shí)間復(fù)雜度為O(nlogn)，空墨盒加墨復(fù)雜度O(n)

for(inti=0;isize;i