堆積(Heap)和二元搜尋樹大致上雷同

1、8-1堆積(Heap)和二元搜尋樹大致上雷同，但有一點點差異。Heap在分類上大致可分為Max-heap, Min-heap, Min-max heap及Deap。Heap也可用在排序上，此稱為Heap sort（堆積排序）。8-28.1 何謂堆積何謂堆積 何謂堆積（Heap）？定義如下：堆積是一棵二元樹，其樹根的鍵值大於子樹的鍵值，而且必須符合第六章6.2節(jié)所談的完整二元樹。8-38.1 何謂堆積何謂堆積 它是一棵Heap，而不是二元搜尋樹。在調(diào)整的過程中有二種方式，一是由上而下，從樹根開始與其子節(jié)點相比，若前者大則不用交換，反之，則要交換；以符合父節(jié)點大於子節(jié)點。8-48.1 何謂堆積何謂

2、堆積8-58.1 何謂堆積何謂堆積 此種方法也可以讓子節(jié)點先比，找出最大者再與其父節(jié)點比，此種方法至多只要做一次對調(diào)即可，如下圖23和30中30較大，因此15和30對調(diào)。由於這種方式較快，故若以由上而下調(diào)整時，皆以此種方式進行之。8-68.1 何謂堆積何謂堆積 一棵Heap不是唯一，因為只要父節(jié)點大於子節(jié)點即可。需在此提醒讀者的是，當中間有某些節(jié)點互換時，需要再往上相比較，直到父節(jié)點大於子節(jié)點為止。8-78.1 何謂堆積何謂堆積 第二種方法為由下而上，先算出此棵樹的節(jié)點數(shù)目，假設(shè)n，再取其，從此節(jié)點，開始與它的最大子節(jié)點相比，若最大子節(jié)點的鍵值大於父節(jié)點之鍵值，則相互對調(diào)，一直做到樹根止。記得

3、相互對調(diào)後要往下繼續(xù)比較，看看是否還要對調(diào)喔！調(diào)整的方法如下：8-88.1 何謂堆積何謂堆積 step 1：先將每一節(jié)點按完整二元樹的順序加以編號如下圖：8-98.1 何謂堆積何謂堆積 step 2： ，故從第2節(jié)點開始與其較大的子節(jié)點相比。由於40比23大，故調(diào)換之。8-108.1 何謂堆積何謂堆積 step 3：接下來將第個節(jié)點與其較大子 節(jié)點比，我們發(fā)現(xiàn)40大於15，故調(diào)換之，如下圖：8-118.1 何謂堆積何謂堆積 step 4：雖然皆已調(diào)換完成，但我們發(fā)現(xiàn)第2節(jié)點小於第4節(jié)點（1523），故需繼續(xù)對調(diào)，如下圖：8-128.1 何謂堆積何謂堆積 承以上的那一棵Heap，加入30及50。

4、 首先按照完整二元樹的特性將30加進來， 如下圖8-138.1 何謂堆積何謂堆積8-148.1 何謂堆積何謂堆積 因為加入50後不是一棵Heap，所以要加以調(diào)整之。 由於原先已是一棵Heap，所以，只要將加入的那一個節(jié)點往上調(diào)整即可。8-158.1 何謂堆積何謂堆積 Heap的刪除則將完整二元樹的最後一節(jié)點取代被刪除的節(jié)點，然後判斷是否為一棵Heap，若否，則再依上述的方法加以調(diào)整之。8-168.1 何謂堆積何謂堆積8-178.1 何謂堆積何謂堆積再刪除40，則將10取代之。8-188.1 何謂堆積何謂堆積再舉一例，有一棵Heap如下：8-198.1 何謂堆積何謂堆積 今欲將40刪除，則以15

5、取代40（因為15在完整二元樹中是最後一個節(jié)點）8-208.1 何謂堆積何謂堆積 此時將15和其所屬的最大子節(jié)點比較，亦即15和35（因為它大於30）比較，直接將15和35交換。8-218.2 何謂何謂min-heap 上述介紹的Heap，我們稱之為max-heap，在max-heap樹中的鍵值，一律是上大於下，節(jié)點內(nèi)的鍵值一律大於其子節(jié)點。其中min-heap的觀念十分簡單，其節(jié)點鍵值一律小於子節(jié)點，恰與max-heap相反，如下圖即為一棵min-heap的例子。8-228.2 何謂何謂min-heap 由於其加入與刪除的方法與max-heap十分類似，在此就不重覆說明了。8-238.3 m

6、in-max heap min-max heap包含了min-heap與max-heap兩種Heap的特徵8-248.3 min-max heap 何謂min-max heap： 為了方便解說，我們就直接以上圖為例，來定義min-max heap，必須符合下列三項定義：8-258.3 min-max heap 1. min-max heap是以一層min-heap， 一層max-heap交互構(gòu)成的。 2. 樹中為min-heap的部分，仍需符合 min-heap的特性。 3. 樹中為max-heap的部分，仍需符合 max-heap的特性。8-268.3 min-max heap min-ma

7、x heap的加入與max-heap的原理差不多，但是加入後，要調(diào)整至符合上述min-max heap的定義。8-278.3 min-max heap8-288.3 min-max heap若加入5，步驟如下：8-298.3 min-max heap 加入後185，不符合第一項定義，將5與18交換。8-308.3 min-max heap 交換後，由於105，不符合第二項定義，將5與10對調(diào)。8-318.3 min-max heap 此時已符合min-max heap的定義，不須再作調(diào)整。8-328.3 min-max heap 若刪除min-max heap的最後一個節(jié)點，則直接刪除即可；否

8、則，先將刪除節(jié)點鍵值與樹中的最後一個節(jié)點對調(diào)，再作調(diào)整動作，亦即以最後一個節(jié)點取代被刪除節(jié)點。假設(shè)已存在一棵min-max heap如下：8-338.3 min-max heap8-348.3 min-max heap若刪除45，則直接刪除。8-358.3 min-max heap 若刪除40，則需以最後一個節(jié)點的鍵值18取代40。8-368.3 min-max heap 交換後1819，不符合第一項定義，將18與19交換。8-378.3 min-max heap 交換後，由於19小於32、28、34、31，不符合第三項定義，必需將19與最大的鍵值34交換。8-388.3 min-max he

9、ap 符合min-max heap的定義，刪除動作結(jié)束。8-398.4 Deap 何謂Deap： Deap同樣也具備max-heap與min-heap的特徵，其定義如下：1.Deap的樹根不儲存任何資料，為一空節(jié)點。2.樹根的左子樹，為一棵min-heap；右子樹則為max-heap。3.min-heap與max-heap存在一對應(yīng)，假設(shè)左子樹中有一節(jié)點為i，則在右子樹中必存在一節(jié)點j與i對應(yīng)，則i必須小於等於j。8-408.4 Deap8-418.4 Deap Deap的加入動作與其它Heap一樣，將新的鍵值加入於整棵樹的最後，再調(diào)整符合Deap的定義，假設(shè)已存在一deap如下：8-428.

10、4 Deap 若加入25，加入後右子樹仍為一棵max-heap，且左子樹對應(yīng)節(jié)點15小於等於它所對應(yīng)的右子樹節(jié)點25，符合deap的定義，加入的結(jié)果如下：8-438.4 Deap加入17，加入後的圖形如下所示：8-448.4 Deap 此時右子樹仍為max-heap，但17小於其左子樹的對應(yīng)節(jié)點20，故將17與20交換。8-458.4 Deap加入40，如下所示：8-468.4 Deap 加入後左子樹雖為min-heap，但40大於其對應(yīng)節(jié)點25（與節(jié)點40的父節(jié)點對應(yīng)之右子樹節(jié)點），不符合deap的定義，故將40與25交換，如下所示：8-478.4 Deap 交換後樹中的右子樹不是一棵max-heap，重新將其調(diào)整為max-heap即可。8-488.4 Deap Deap的刪除動作與其它Heap一樣，當遇到刪除節(jié)點非最後一個節(jié)點時，要以最後一個節(jié)點的鍵值取代刪除節(jié)點，並調(diào)整至符合deap的定義，假設(shè)存在Deap如下：8-498.4 Deap8-508.4 Deap 若刪除29，則直接刪除即可，結(jié)果如下圖所示：8-518.4 Deap 刪除21，此時以最後一個節(jié)點22取代之，再將最後一個節(jié)點刪除，檢查左子樹仍為一棵min-heap，且節(jié)點鍵值22小於其對應(yīng)節(jié)點32，不