《數(shù)據(jù)結(jié)構(gòu)-用C語(yǔ)言描述》第八章 堆

第8章堆21世紀(jì)高等院校規(guī)劃教材返回總目錄1?

2006堆2?

2006了解堆與其的插入和刪除操作關(guān)于min-heap關(guān)于min-max

heap

及其插入和刪除操作關(guān)于Deap及其插入和刪除操作什么是堆3?

2006堆（Heap）和二叉查找樹大致相同。堆的定義如下：堆是一棵二叉樹，其樹根的鍵值大于子樹的鍵值，而且必須是完全二叉樹。不管左子樹和右子樹的大小順序，這是堆與二叉查找樹最大的差異。大致可分為：Max-heap、Min-Max

heap及Deap堆具有新增、刪除、輸出數(shù)據(jù)3個(gè)功能堆（Heap）的插入4?

2006例：在一棵Heap中插入30及50 步驟如下：按照完全二叉樹的特性將30插進(jìn)來(lái)，如圖8-9所示。插入50，但是此時(shí)已經(jīng)不是一棵Heap，要進(jìn)行調(diào)換。進(jìn)行調(diào)換后，將要插入的那一個(gè)節(jié)點(diǎn)往上調(diào)整即可，如圖8-10所示。堆（Heap）的插入—示意圖Heap示圖5?

2006圖8-9插入30后的完全二叉樹狀態(tài)圖圖8-10插入50后的完全二叉樹狀態(tài)圖堆（Heap）的刪除Heap的刪除：-Heap的刪除則將完全二叉樹的最后一節(jié)點(diǎn)取代被刪除的節(jié)點(diǎn)，然后判斷是否為一棵Heap，若不是，則再依照上述方法進(jìn)行調(diào)整。刪除30后的調(diào)整方法如圖8-11所示。圖8-116?

2006刪除30后的調(diào)整方法什么是min-Heap堆除了max-heap外，還可細(xì)分為min-heap、min-max-heap、deap等。min-heap的概念十分簡(jiǎn)單，其節(jié)點(diǎn)鍵值一律小于小節(jié)點(diǎn)，恰與max-heap相反，如圖8-22所示即為min-heap的一個(gè)例子。圖8-227?

2006min-heap示意圖min-max

heap的定義min-max-heap包含了min-heap與max-heap兩種堆的特征，如圖8-27所示即為一棵min-max-heap：8?

2006min-max

heap的定義9?

2006min-max-heap必須符合下列3項(xiàng)定義：■■■—min-max-heap是以一層min-heap、一層max-heap 交互構(gòu)成的—樹中為min-heap的部分，仍需符合min-heap的特 性—樹中為max-heap的部分，仍需符合max-heap的特 性min-max

heap的插入10?

2006雖然max-max-heap的插入與max-heap的原理差不多，但是插入后，要調(diào)整至符合min-max-heap的定義。例：假設(shè)已存在一棵min-max-heap，如圖8-28所示?！觥鱿蚱洳迦?的操作步驟如下：（1）插入5，如圖8-29所示；（2）進(jìn)行調(diào)整：插入5后18>5,不符合定義第一項(xiàng)；（3）再次進(jìn)行調(diào)整：當(dāng)步驟（2）調(diào)整后10>，不符合定義第二 項(xiàng)；（4）操作結(jié)束，符合min-max-heap的定義。min-max

heap的插入圖8-28min-max-heap示意圖圖8-29插入5后的示意圖圖8-30插入5■5■與■18■交■換5與10交換圖8-31交換5和10后的示意圖11交換5和18后的示意圖?

2006min-max

heap的刪除12?

2006min-max-heap的刪除同min-max-heap的插入一樣，其結(jié)果要符合定義。若刪除min-max-heap的最后一個(gè)節(jié)點(diǎn)，則直接刪除即可；否則，先將刪除節(jié)點(diǎn)鍵值與樹中的最后一個(gè)節(jié)點(diǎn)對(duì)調(diào)，再做調(diào)整操作，即以最后一個(gè)節(jié)點(diǎn)取代被刪除節(jié)點(diǎn)。DeapDeap同樣也具備max-heap與min-heap的特征。圖8-41

Deep示意圖13?

2006Deap其定義如下：（1）Deap的樹根不儲(chǔ)存任何數(shù)據(jù)，為一空節(jié)點(diǎn)。（2）樹根的左子樹，為一棵min-heap；右子樹則為max-heap。（3）min-heap與max-heap存在對(duì)應(yīng)關(guān)系。Deap的插入和刪除14?

2006Deap的插入操作與