第C語言堆與二叉樹的順序結構與實現目錄一.二叉樹的順序結構二.堆的概念及結構三.堆的實現四.堆排序(具有缺陷型)

一.二叉樹的順序結構

普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。

二.堆的概念及結構

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

堆的性質：

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

三.堆的實現

將要實現的接口及堆的創建：

（由于堆的特點，這里使用數組結構實現）

//將要實現的是大堆

typedefintHPDataType;

//創建堆結構體

typedefstructHeap

HPDataType*arr;//數組存儲

size_tcapacity;//容量

size_tsize;//堆里的元素個數

//初始化堆

voidHeapInit(HP*php);

//銷毀堆

voidHeapDestroy(HP*php);

voidswap(HPDataType*pa,HPDataType*pb);

//插入堆，后面插入

voidHeapPush(HP*php,HPDataTypex);

//刪除堆元素，第一個元素

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;

}

堆的銷毀

voidHeapDestroy(HP*php)

assert(php);

//銷毀數組

free(php-arr);

php-arr=NULL;

php-capacity=php-size=0;

}

交換函數

voidswap(HPDataType*pa,HPDataType*pb)

HPDataTypetemp=*pa;

*pa=*pb;

*pb=temp;

}

堆的插入

這里的插入是在堆的最后面插入，堆不能任意位置插入會破壞堆的結構，這里最后面插入也會面臨一個問題，插入必須還是大堆，那就要使用向上調整法

接下來插入一個70，由于70最大，所以會使用到向上調整法，如下圖：

將新插入進來的元素與父節點對比，如果父節點小于子節點，就交換，依次往下進行，否則就不用交換，終止向上調整

//向上調整法

voidAdjustUp(HPDataType*arr,size_tchild)

//父節點

HPDataTypeparent=(child-1)/2;

//交換

while(child0)//用child控制，parent會死循環

//如果父節點更大，說明需要更換

if(arr[parent]arr[child])

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

//孩子和父親都往上走

child=parent;

parent=(child-1)/2;

voidHeapPush(HP*php,HPDataTypex)

assert(php);

//擴容

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;

//需要將孩子穿過去，注意size是在最后一個位置的后一個位置

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

}

堆的刪除

堆的刪除刪除的是堆頂的元素，但是不能盲目的將第一個元素刪除，然后將后面的元素往前覆蓋，因為當數組里的元素沒有順序時，就會破壞了堆的結構，所以這里需要用到向下調整算法

在插入的基礎上，刪除掉堆頂的數，也就是70，此時就要使用到向下調整法，如下圖：

因為我們刪除的是堆頂的元素，所以可以這樣

先將堆頂元素和最后一個元素進行交換，再刪除交換后的堆尾的元素，此時的堆頂元素因為不知道大小，所以將其和自己的兩個孩子中最大的比較，如果堆頂的元素小就交換，依次往下進行，否則就不交換，結束向下調整

voidAdjustDown(HPDataType*arr,size_tparent,size_tsize)

//假設左孩子最小

HPDataTypechild=(parent*2)+1;

//使用child控制，parent會越界

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;

//當出現父親小于孩子時，說明不用往下遍歷了

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;

//向下調整

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];

}

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

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

intmain()

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

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

HPhp;//創建堆

HeapInit(hp);//初始化

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

for(inti=0;isize;i