目錄

1.順序結(jié)構(gòu)

2.示意圖

??編輯

從物理結(jié)構(gòu)還原為邏輯結(jié)構(gòu)的方法

3.父子節(jié)點(diǎn)編號(hào)的規(guī)律

4.順序存儲(chǔ)的前提條件

5.堆的簡(jiǎn)介

堆的定義

堆的兩個(gè)重要性質(zhì)

小根堆和大根堆?

6.堆的插入

7.堆的實(shí)現(xiàn)及操作堆的函數(shù)

堆的結(jié)構(gòu)體定義

堆初始化函數(shù)HeapInit

堆插入元素函數(shù)HeapPush

堆向上調(diào)整函數(shù)AdjustUp

寫(xiě)法1

寫(xiě)法2

寫(xiě)法3

提問(wèn)

向上調(diào)整的前提

測(cè)試堆插入函數(shù)

---

1.順序結(jié)構(gòu)

存儲(chǔ)二叉樹(shù)的兩種結(jié)構(gòu):一種順序結(jié)構(gòu),一種鏈?zhǔn)浇Y(jié)構(gòu)本文講順序結(jié)構(gòu)

---

2.示意圖

?

上方圖中的數(shù)字0~6代表各個(gè)節(jié)點(diǎn)的編號(hào)?

邏輯結(jié)構(gòu):方便人理解的結(jié)構(gòu) 物理結(jié)構(gòu):實(shí)實(shí)在在存儲(chǔ)的結(jié)構(gòu)

可見(jiàn)順序結(jié)構(gòu)的底層是用數(shù)組(連續(xù))存儲(chǔ)的

從物理結(jié)構(gòu)還原為邏輯結(jié)構(gòu)的方法

對(duì)于滿二叉樹(shù)而言,

第一層有一個(gè)節(jié)點(diǎn),第二層有兩個(gè)節(jié)點(diǎn),第一層有四個(gè)節(jié)點(diǎn)......

則可按層拆分

再組合

加上線

?對(duì)于完全二叉樹(shù)而言,做法和上述類(lèi)似,不再贅述

3.父子節(jié)點(diǎn)編號(hào)的規(guī)律

比如求F的父節(jié)點(diǎn),如果畫(huà)圖則太慢,其實(shí)可以看出規(guī)律

F編號(hào)為5,其父節(jié)點(diǎn)C編號(hào)為2;E編號(hào)為4,其父節(jié)點(diǎn)B編號(hào)為1;

發(fā)現(xiàn)(注:為高斯函數(shù),又稱(chēng)向下取整函數(shù))

★★★求父節(jié)點(diǎn)b編號(hào)的公式:

在C語(yǔ)言中為father = (child-1)/2;father獲得表達(dá)式的商

如果給出父節(jié)點(diǎn)的編號(hào),求左孩子和右孩子的編號(hào)

父節(jié)點(diǎn)C編號(hào)為2,則左孩子F的編號(hào)為2*2+1,則右孩子G的編號(hào)為2*2+2

★★★求孩子節(jié)點(diǎn)編號(hào)的公式:左孩子:? 右孩子:

4.順序存儲(chǔ)的前提條件

結(jié)論:完全二叉樹(shù)(含滿二叉樹(shù))適合用順序存儲(chǔ)

如果非完全二叉樹(shù),存儲(chǔ)會(huì)浪費(fèi)空間

5.堆的簡(jiǎn)介

堆的定義

如果有一個(gè)關(guān)鍵碼的集合，把它的所有元素按完全二叉樹(shù)的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，并滿足： 且 且 (i=0,1,2,3,..,n)則稱(chēng)為小堆(或大堆)

堆的兩個(gè)重要性質(zhì)

• 堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值；

• 堆總是一棵完全二叉樹(shù)

小根堆和大根堆?

小根堆:樹(shù)中所有的父節(jié)點(diǎn)的值都小于或等于孩子節(jié)點(diǎn)的值

大根堆:樹(shù)中所有的父節(jié)點(diǎn)的值都大于或等于孩子節(jié)點(diǎn)的值

如果樹(shù)中所有的父節(jié)點(diǎn)的值都等于孩子節(jié)點(diǎn)的值,則既為小根堆又為大根堆

注:等定義中并沒(méi)有規(guī)定左孩子和右節(jié)點(diǎn)的值的大小關(guān)系,因此堆不一定有序

6.堆的插入

由堆的簡(jiǎn)介可知:堆是一個(gè)完全二叉樹(shù),因此可以用順序結(jié)構(gòu)實(shí)現(xiàn)

以下方大根堆為例

現(xiàn)要尾插數(shù)字20,由存儲(chǔ)結(jié)構(gòu)可以看出:空間不夠,要擴(kuò)容

插入20前,找其父節(jié)點(diǎn)(),發(fā)現(xiàn)后者值為30,可以插入,仍然滿足大根堆的性質(zhì)?

再尾插入60

發(fā)現(xiàn)不滿足大根堆的性質(zhì),需要一次調(diào)整

發(fā)現(xiàn)調(diào)整后仍然不滿足大根堆的性質(zhì)(56<60),需要再一次調(diào)整?

發(fā)現(xiàn)調(diào)整后滿足大根堆的性質(zhì)(56<60<70),結(jié)束

上述的調(diào)整起名為向上調(diào)整,最多調(diào)整h(二叉樹(shù)的高度)次

7.堆的實(shí)現(xiàn)及操作堆的函數(shù)

以大根堆為例

堆的結(jié)構(gòu)體定義

可以用結(jié)構(gòu)體來(lái)定義堆,由于堆的底層是用數(shù)組存儲(chǔ)的,因此三個(gè)成員變量:數(shù)據(jù)域,大小size,容量capacity

寫(xiě)入頭文件中

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

堆初始化函數(shù)HeapInit

要想使用堆必須先初始化堆(malloc,對(duì)size和capacity初始化值)

void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc");return;}php->size = 0;php->capacity = 4;
}

php->capacity跟隨malloc函數(shù)開(kāi)辟空間的大小

堆插入元素函數(shù)HeapPush

插入前先判斷空間是否充足,不夠則relloc原來(lái)的2倍.之后調(diào)用向上調(diào)整函數(shù)進(jìn)行插入

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("realloc");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;//插入至數(shù)組的最后一個(gè)元素的下一個(gè)位置(size)php->size++;//數(shù)組大小+1//調(diào)用向上調(diào)整函數(shù)AdjustUp(php->a,php->size-1);
}

注意到AdjustUp傳的第二個(gè)參數(shù)是php->size-1

堆向上調(diào)整函數(shù)AdjustUp

如果a[parent] < a[child],則進(jìn)行交換,之后調(diào)整parent和child的值,以便于下一次調(diào)整

寫(xiě)法1

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (a[parent] < a[child]){Swap(&a[parent], &a[child]);//調(diào)整parent和child的值child = parent;parent = (parent - 1) / 2;}
}

寫(xiě)法2

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (parent>=0){if (a[child] > a[parent]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}

寫(xiě)法3

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child] > a[parent]){Swap(&a[parent], &a[child]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}

提問(wèn)

已知這幾種寫(xiě)法都能成功運(yùn)行,哪個(gè)寫(xiě)法存在不規(guī)范的地方?

答:從特殊情況考慮問(wèn)題,寫(xiě)法2:

當(dāng)parent==0時(shí),進(jìn)入循環(huán),若child==1,if判斷成立,交換值后,child==0,parent==-1/2==0(取商)

while(parent>=0)條件仍然成立,但不滿足if (a[child] > a[parent]),因此break

不規(guī)范的地方:child==parent==0就沒(méi)有必要再次進(jìn)入循環(huán),建議改成while (child>0)(寫(xiě)法3)

向上調(diào)整的前提

除了child位置,前面的數(shù)據(jù)結(jié)構(gòu)構(gòu)成堆

測(cè)試堆插入函數(shù)

main.c手動(dòng)寫(xiě)入插入一些隨機(jī)值,以下代碼,下斷點(diǎn)至return 0;

#include "Heap.h"
int main()
{HP hp;HeapInit(&hp);HeapPush(&hp, 1);HeapPush(&hp, 3);HeapPush(&hp, 0);HeapPush(&hp, 5);HeapPush(&hp, 8);HeapPush(&hp, 12);HeapPush(&hp, 2);HeapPush(&hp, 5);HeapPush(&hp, 30);HeapPush(&hp, 50);return 0;}

打開(kāi)監(jiān)視窗口查看

畫(huà)圖后發(fā)現(xiàn)符合大根堆的性質(zhì)