堆積(Heap Tree) 授課老師：蕭志明.

Presentation on theme: "堆積(Heap Tree) 授課老師：蕭志明."— Presentation transcript:

1 堆積(Heap Tree) 授課老師：蕭志明

2 何謂堆積 堆積(Heap)和二元搜尋樹大致上雷同，但有一點點差異。
Heap在分類上大致可分為Max-heap, Min-heap, Min-max heap及Deap。 Heap也可用在排序上，此稱為Heap sort（堆積排序）。

3 Definition 最大樹 ( max tree ) 是一種樹，其中每一個節點的值不小於它的子節點 ( 如果存在的話 ) 的鍵值。
最大累堆 ( max heap ) 為一種也是最大樹的完整二元樹。　　 最小樹 ( min  tree ) 是一種樹，其中每一個節點的值不大於它的子節點 ( 如果存在的話 ) 的鍵值。　　最小累堆 ( min heap ) 為一種也是最小樹的完整二元樹。

4 堆積範例

5 堆積範例

6 何謂堆積 它是一棵Heap，而不是二元搜尋樹。在調整的過程中有二種方式： 一是由上而下，從樹根開始與其子節點相比，若前者大則不用交換
，反之，則要交換；以符合父節點大於子節點。

7 堆積操作

8 堆積操作 此種方法也可以讓子節點先比，找出最大者再與其父節點比，此種方法至多只要做一次對調即可，如下圖23和30中30較大，因此15和30對調。由於這種方式較快，故若以由上而下調整時，皆以此種方式進行之。

9 何謂堆積 一棵Heap不是唯一，因為只要父節點大於子節點即可。需在此提醒讀者的是，當中間有某些節點互換時，需要再往上相比較，直到父節點大於子節點為止。

10 基本的堆積樹演算法 堆積樹有二個基本的維護作業： 新增。 刪除。 對堆積樹進行追蹤、搜尋與列印，是沒有意義的。
在這一方面，它比較像是一個限制資料結構。 Heap也可用在排序上，此稱為Heap sort（堆積排序）。

11 基本的堆積樹演算法 為了實作新增與刪除作業，需要二個基本的演算法： 重新向上堆積 重新向下堆積。

12 重新向上堆積 (ReheapUp) 假設一個類完全二元樹包含N個節點，其中N-1個節點滿足堆積樹的順序性質，但是最後一個節點不滿足。
換句話說，倘使最後一個節點不存在，則此結構即成為一個堆積樹。 重新向上堆積 (ReheapUp)，將最後一個節點往上移動，直到它位於正確的位置，以符合堆積的定義。 圖9-4顯示調整的情況，在進行重新向上堆積樹之前，最後一個節點的順序不對。而在操作之後，它會位於正確的位置，因此堆積樹也就多了一個節點。

13 重新向上堆積 (ReheapUp) 新增在葉節點進行。
堆積樹是一個完全或類完全樹，新節點必須放在葉階層的第1個(最左邊)空位，如圖9-4所示。 如果新節點的鍵值大於父節點，就交換兩者的資料與鍵值，將新節點往上移動。 經由不斷地改變子－父節點的鍵值與資料，新節點最後會到達正確的位置。 重新向上堆積 (ReheapUp) 藉由將最後一個節點向上移動，直到它位於正確的位置，以修復堆積樹的結構。

14 圖 重新向上堆積作業

15 重新向上堆積 (ReheapUp) 圖9-5追蹤ReheapUp操作。 依定義25比父節點12的左子樹的所有鍵值都大。於是將25與12交換。
接著發現25依然大於其父節點21，所以再交換一次。 最後目標節點鍵值25小於父節點鍵值42，表示找到正確的位置，整個操作結束。

16 圖 重新向上堆積範例

17 重新向下堆積 (ReheapDown) 重新向下堆積 (ReheapDown) 假設一個類完全二元樹，除了根節點之外，滿足堆積樹的順序性質。
這會發生在刪除根節點時，剩下兩個堆積樹。 為了修正這種情況，將最後一個節點資料移到根節點。很明顯地，這會破壞堆積樹的性質。 重新向下堆積 (ReheapDown) 由根節點向下移動，一直找到它正確的位置為止。 為了修復結構，需要將根節點向下移動，直到它的位置符合堆積樹的順序規定。 們稱此作業為重新向下堆積(ReHeapDown)，如圖9-6所示。

18 圖 重新向下堆積的例子

19 重新向下堆積 (ReheapDown) 圖9-7顯示重新向下堆積的作業過程。
開始時，根節點10小於其子樹，所以要檢查左右子樹，並選擇比較大的子樹32，與根節點作 交換。 圖9-7(b) 顯示交換之後的情況，繼續檢查子樹以判斷是否可以結束作業，發現10小於其子樹，所以要將10與比較大的子樹30作交換。 此時，已到達葉節點，所以可以結束作業。

20 圖 重新向下堆積

21 Heap的加入

22 Heap的加入 加入30及50。 首先按照完整二元樹的特性將30加進來， 如下圖

23 Heap的加入 因為加入50後不是一棵Heap，所以要加以調整之。 由於原先已是一棵Heap，所以，只要將加入的那一個節點往上調整即可。

24 Heap的刪除 Heap的刪除則將完整二元樹的最後一節點取代被刪除的節點，然後判斷是否為一棵Heap，若否，則再依上述的方法加以調整之。

25 Heap的刪除

26 Heap的刪除

27 Heap的刪除 再刪除40，則將10取代之。

28 堆積練習 再舉一例，有一棵Heap如下：

29 堆積練習 今欲將40刪除，則以15取代40（因為15在完整二元樹中是最後一個節點）

30 堆積練習 此時將15和其所屬的最大子節點比較，亦即15和35（因為它大於30）比較，直接將15和35交換。

31 何謂min-heap 上述介紹的Heap，我們稱之為max-heap，在max-heap樹中的鍵值，一律是上大於下，節點內的鍵值一律大於其子節點。其中min-heap的觀念十分簡單，其節點鍵值一律小於子節點，恰與max-heap相反，如下圖即為一棵min-heap的例子。

32 何謂min-heap 由於其加入與刪除的方法與max-heap十分類似，在此就不重覆說明了。

33 min-max heap min-max heap包含了min-heap與max-heap兩種Heap的特徵

34 min-max heap

35 min-max heap 何謂min-max heap：
1.min-max heap是以一層min-heap，一層max-heap交互構成的。 2.樹中為min-heap的部分，仍需符合min-heap的特性。 3.樹中為max-heap的部分，仍需符合 max-heap的特性。

36 min-max heap的加入 min-max heap的加入與max-heap的原理差不多，但是加入後，要調整至符合上述min-max heap的定義。

37 min-max heap的加入

38 min-max heap的加入 若加入5，步驟如下：

39 min-max heap的加入 加入後18>5，不符合第一項定義，將5與18交換。

40 min-max heap的加入 交換後，由於10>5，不符合第二項定義，將5與10對調。

41 min-max heap的刪除 若刪除min-max heap的最後一個節點，則直接刪除即可；否則，先將刪除節點鍵值與樹中的最後一個節點對調，再作調整動作，亦即以最後一個節點取代被刪除節點。假設已存在一棵min-max heap如下：

42 min-max heap的刪除

43 min-max heap的刪除

44 min-max heap的刪除 若刪除45，則直接刪除。

45 min-max heap的刪除 若刪除40，則需以最後一個節點的鍵值18取代40。

46 min-max heap的刪除 交換後18<19，不符合第一項定義，將18與19交換。

47 min-max heap的刪除 交換後，由於19小於32、28、34、31，不符合第三項定義，必需將19與最大的鍵值34交換。

48 Deap Deap同樣也具備max-heap與min-heap的特徵，其定義如下： 1.Deap的樹根不儲存任何資料，為一空節點。
2.樹根的左子樹，為一棵min-heap；右子樹則為max-heap。 3.min-heap與max-heap存在一對應，假設左子樹中有一節點為i，則在右子樹中必存在一節點j與i對應，則i必須小於等於j。

49 Deap

50 Deap

51 Deap的加入 Deap的加入動作與其它Heap一樣，將新的鍵值加入於整棵樹的最後，再調整符合Deap的定義。

52 Deap的加入 假設已存在一deap如下：

53 Deap的加入 若加入25，加入後右子樹仍為一棵max-heap，且左子樹對應節點15小於等於它所對應的右子樹節點25，符合deap的定義，加入的結果如下：

54 Deap的加入 加入17，加入後的圖形如下所示：

55 Deap的加入 此時右子樹仍為max-heap，但17小於其左子樹的對應節點20，故將17與20交換。

56 Deap的加入 加入40，如下所示：

57 Deap的加入 加入後左子樹雖為min-heap，但40大於其對應節點25（與節點40的父節點對應之右子樹節點），不符合deap的定義，故將40與25交換，如下所示：

58 Deap的加入 交換後樹中的右子樹不是一棵max-heap，重新將其調整為max-heap即可。

59 Deap的刪除 Deap的刪除動作與其它Heap一樣，當遇到刪除節點非最後一個節點時，要以最後一個節點的鍵值取代刪除節點，並調整至符合deap的定義。

60 Deap的刪除

61 Deap的刪除

62 Deap的刪除 若刪除29，則直接刪除即可，結果如下圖所示：

63 Deap的刪除 刪除21，此時以最後一個節點22取代之，再將最後一個節點刪除，檢查左子樹仍為一棵min-heap，且節點鍵值22小於其對應節點32，不需作任何調整。刪除結果如下：

64 Deap的刪除

65 Deap的刪除 刪除12，以最後一個節點27取代。

66 Deap的刪除 左子樹不符合min-heap的定義，將27子節點中鍵值較小者16交換。

67 Deap的刪除 最後16與其對應的30比較；16小於30，並且27也小於它所對應max-heap那邊的30，故不需再做調整。