第十一章 Heap 結構

目次 11.1 Min-Max heap 11.2 Deap 11.3 Binomial heap 11.4 Fibonacci heap 11.5 動動腦時間 11.6 練習題解答

11.1 Min-max heap Min-max heap 它包含了 min-heap 與 max-heap 兩種堆積樹的特徵，如下圖即為一棵min-max heap： Level 1 Level 2 Level 3 Level 4 10 40 45 19 13 18 15 32 28 34 31 24 35 42 33 min max

11.1 Min-max heap (con.t) Min-max heap 的特性 min-max heap是以一層min-heap、max-heap交互構成的 Level1中各節點的鍵值一律小於子節點(10小於40、45)， Level2中各節點的鍵值一律大於子節點(40大於19、13；45大於18、15) 樹中為min-heap的部分，仍需符合min-heap的特性 如圖Level 1的節點鍵值，會小於Level為3的子樹(10小於19、13、18、15) 樹中為max-heap的部份，仍需符合max-heap的特性 如圖的Level 2的節點鍵值，會大於Level為4之子樹(40大於32、28、34、31；45大於24、35、42、33)

11.1 Min-max heap (con.t) 11.1.1 Min-max heap的加入 min-max heap的加入 10 40 45 19 13 18 15 32 28 34 31

11.1 Min-max heap (con.t) 若加入5，步驟如下 min max 40 45 19 13 18 15 32 28 34 31 5 10

11.1 Min-max heap (con.t) 加入後18>5，不符合第一項定義，將5與18交換 min max 40 45 19 13 5 15 32 28 34 31 18 10

11.1 Min-max heap (con.t) 交換後，由於10>5，不符合第二項定義，將5與10對調 min max 40 45 19 13 10 15 32 28 34 31 18 5

11.1 Min-max heap (con.t) 符合min-max heap的定義，加入動作結束。若再加入50，其加入步驟如下 ： 40 45 19 13 10 15 32 28 34 31 18 5 50

11.1 Min-max heap (con.t) 加入後45<50，不符合第三項定義，將45與50交換 40 50 19 13 10 15 32 28 34 31 18 5 45 min max

11.1 Min-max heap (con.t) 11.1.2 Min-max heap的刪除 min-max heap的刪除 若刪除最後一個節點，則直接刪除即可 否則，先將刪除節點鍵值與樹中的最後一個節點對調，再作調整動作，意即以最後一個節點取代被刪除節點 假設已存在一棵min-max heap如下： 40 50 19 13 10 15 32 28 34 31 18 5 45 min max

11.1 Min-max heap (con.t) 若刪除45，則直接刪除 min max 40 50 19 13 10 15 32 28 34 31 18 5

11.1 Min-max heap (con.t) 若刪除40，則需以最後一個節點的鍵值18取代40 min max 18 50 19 13 10 15 32 28 34 31 5

11.1 Min-max heap (con.t) 交換後18<19，不符合第一項定義，將18與19交換 19 50 18 13 10 15 32 28 34 31 5 min max

11.1 Min-max heap (con.t) 交換後，由於19小於32、28、34、31，不符合第三項定義，將19與最大的鍵值34交換 50 18 13 10 15 32 28 19 31 5 min max

11.2 Deap Deap 同樣也具備max-heap與min-heap的特徵，其定義如下： Deap的樹根不儲存任何資料，為一空節點。 樹根的左子樹為一棵min-heap；右子樹則為max-heap。 min-heap與max-heap存在一對應，假設左子樹中有一節點為i，則在右子樹中相同的位置存在一節點 j與 i 對應，且i必須小於等於 j。如圖的5與35對應，5小於35；12與30對應，12小於30 5 35 12 21 30 32 18 16 25 27 22 29

11.2 Deap (con.t) 11.2.1 Deap 的加入 Deap 的加入 假設已存在一 Deap 如下： 5 30 15 20

11.2 Deap (con.t) 若加入25，加入後右子樹仍為一棵max-heap，如下所示，且左子樹對應節點15小於等於它所對應的右子樹節點25，符合deap的定義 5 30 15 20 25

11.2 Deap (con.t) 加入17，加入後的圖形如下所示 此時右子樹仍為max-heap，但17小於其左子樹的對應節點20，故將17與20交換 5 30 15 20 25 17 5 30 15 17 25 20

11.2 Deap (con.t) 加入40，如下所示 5 30 15 17 25 20 40

11.2 Deap (con.t) 加入後左子樹雖為min-heap，但40大於其對應節點25(與節點40的父節點對應之右子樹節點)，不符合deap的定義，故將40與25交換，如下所示： 5 30 15 17 40 20 25

11.2 Deap (con.t) 交換後樹中的右子樹不是一棵max-heap，重新將其調整為max-heap即可 5 40 15 17 30 20 25

11.2 Deap (con.t) 11.2.2 Deap 的刪除 Deap 的刪除 假設存在一deap如下： 5 35 12 21 30 32 18 16 25 27 22 29

11.2 Deap (con.t) 若刪除29，則直接刪除即可，結果如下圖所示 5 35 12 21 30 32 18 16 25 27 22

11.2 Deap (con.t) 刪除21，此時以最後一個節點22取代之，再將最後一個節點刪除，檢查左子樹仍為一棵min-heap，且節點鍵值22小於其對應節點32，不需作任何調整。刪除結果如下 5 35 12 22 30 32 18 16 25 27

11.2 Deap (con.t) 刪除12，以最後一個節點27取代 5 35 27 22 30 32 18 16 25

11.2 Deap (con.t) 左子樹不符合min-heap的定義，將27子節點中鍵值較小者16交換 最後16與其對應的30比較；16小於30，故不需再做調整 5 35 16 22 30 32 18 27 25

11.3 Binomial heap Binomial heap Binomial heap是由一些Binomial tree所組成的集合 一棵Binomial tree (Bk)具有那些特徵： Bk的Binomial tree含有二棵Bk-1的Binomial tree。 Bk的Binomial tree具有2k的節點數，如下所示 B0 B1 B2 B3

11.3 Binomial heap (con.t) Bk的高度為 k，如 B3 表示此棵Binomial tree的高度為3 在高度為i的那一層共有 k! / i!(k-i)! 個節點 高度 1 2 3

11.3 Binomial heap (con.t) 11.3.1 合併的動作 假設有二棵Binomial heap，如下圖所示： 7 13 11.3.1 合併的動作 假設有二棵Binomial heap，如下圖所示： 7 13 19 15 1 23 12 head[H1] 5 45 19 39 28 44 31 3 37 18 head[H2] 50

11.3 Binomial heap (con.t) 將它們化為一棵Binomial heap，由左至右按照其degree由小至大排列之 6 45 30 10 44 31 1 23 18 head[H] 50 12 3 37 28 13 7 15 19

11.3 Binomial heap (con.t) 將degree相同的合併，並且注意較小的鍵值放在上面，重複此步驟直到沒有相同的degree為止。首先將degree為0的Binomial tree合併 6 45 30 10 44 31 1 23 18 head[H] 50 12 3 37 28 13 7 15 19

11.3 Binomial heap (con.t) 再將degree為1的Binomial tree合併，由於有3棵Binomial tree的degree為1，因此我們必須先判斷root的鍵值為較小的二棵Binomial tree，然後將這二棵Binomial tree中較大的加在較小的Binomial tree下方，如下圖所示： 6 45 30 10 44 31 1 23 18 head[H] 50 12 3 37 28 13 7 15 19

11.3 Binomial heap (con.t) 再將degree為2的合併 6 45 30 10 44 31 1 23 18 head[H] 50 12 3 37 28 13 7 15 19

11.3 Binomial heap (con.t) 再將degree為3的合併 此時就大功告成了，其Big-O為O( log n) 6 45 30 10 44 31 1 23 18 head[H] 50 12 3 37 28 13 7 15 19

11.3 Binomial heap (con.t) 11.3.2 加入的動作 將一節點加入到Binomial heap，有二個步驟： 11.3.2 加入的動作 將一節點加入到Binomial heap，有二個步驟： 將它加入到head[H]指向Binomial tree之樹根的鏈結串列中 執行合併的動作。

11.3 Binomial heap (con.t) 下面舉個例子來說明上述的步驟，將圖11.1加入一節點，其鍵值為18，則加入於head[H]指向的樹根串列中 7 11 8 13 15 17 1 23 18 head[H] 28 12 10 16 19

11.3 Binomial heap (con.t) 利用上述合併的動作，將按照degree的大小排列，再進行合併 由於12和18的degree皆為0，故合併之，將18加入到12的下方，因為18大於12。其Big-O為O( log n) 7 11 8 13 15 17 1 23 18 head[H] 28 12 10 16 19

11.3 Binomial heap (con.t) 11.3.3 刪除的動作 刪除的動作 如有一棵Binomial heap如下 ： 11.3.3 刪除的動作 刪除的動作 一般刪除的動作乃是擷取此棵Binomial heap的最小值出來，因此只要從head[H]指向的鏈結串列中就可找到最小的值在那一棵Binomial tree，此時將此節點刪除之即可 如有一棵Binomial heap如下 ： 7 11 8 13 15 17 1 23 head[H] 28 12 10 16 19

11.3 Binomial heap (con.t) 將最小的鍵值1刪除，則為 7 11 8 13 15 17 10 16 head[H] 28 12 23 19

11.3 Binomial heap (con.t) 因為在刪除1之後，Binomial heap中有degree相同的Binomial tree，因此要執行合併的動作 7 11 8 13 15 17 10 16 head[H] 28 12 23 19

11.3 Binomial heap (con.t) 而刪除動作的Big-O也是O( log n) 7 11 8 13 15 17 10 16 head[H] 28 12 23 19

11.4 Fibonacci heap Fibonacci heap的類型 有一棵F-heap如下所示： max F-heap：若parent節點的鍵值皆大於child節點的鍵值，則稱此棵樹為max F-heap min F-heap：若parent節點的鍵值皆小於child節點的鍵值，則稱此棵樹為min F-heap 有一棵F-heap如下所示： 20 37 18 22 42 39 2 50 6 16 31 12 15 36 min[H]

11.4 Fibonacci heap (con.t) 每一節點的資料結構如下： parent Llink key Rlink Children

11.4 Fibonacci heap (con.t) 11.4.1 加入的動作 加入的動作 假設現在有一棵F-heap，如下圖所示 20 11.4.1 加入的動作 加入的動作 假設現在有一棵F-heap，如下圖所示 20 37 28 22 42 39 2 50 6 16 31 12 15 36 min[H]

11.4 Fibonacci heap (con.t) 加入77 只要將77加入到root串列中，再看看它是否比min[H]來得小，若是，則將min[H]指向此新加入的鍵值。加入後不需要作合併的動作。而此加入動作的Big-O為O(1) 20 37 28 22 42 39 2 50 77 16 31 6 15 36 min[H] 12

11.4 Fibonacci heap (con.t) 11.4.2 擷取F-heap 中的最小值 擷取F-heap 中的最小值 擷取min[H]所指向的節點 假設有一F-heap，如下圖所示： 今將擷取min[H]即為鍵值為2的節點 20 37 22 42 39 2 50 6 16 31 36 min[H]

11.4 Fibonacci heap (con.t) 刪除鍵值2的節點後，此時的F-heap為 20 37 22 42 36 39 50 16 31 6 min[H]

11.4 Fibonacci heap (con.t) 因為刪除鍵值2後，有相同的degree的樹，所以將其合併之。合併的動作與Binomial heap的合併動作相同，在此不再贅述 20 50 22 42 36 39 6 31 16 37 min[H] 20 37 22 42 36 39 16 31 6 50 min[H] 

11.4 Fibonacci heap (con.t) 而刪除動作的Big-O為O( log n)  20 22 42 36 39 31 50 16 37 min[H] 

11.4 Fibonacci heap (con.t) 而刪除動作的Big-O為O( log n)  20 22 42 36 39 31 50 16 37 min[H] 

11.4 Fibonacci heap (con.t) 11.4.3 減少某鍵值的值 減少某鍵值的值 11.4.3 減少某鍵值的值 減少某鍵值的值 將圖11.2的鍵值16減少15，使其為1。 首先與parent node相比，若較小，則刪除此節點與父節點和兄弟節點的指標，此時將此節點和其子節點(若有的話)獨立出來，並將其加入root集合中。 並重新掃瞄root串列中的最小值為何，之後將min[H]指向它

11.4 Fibonacci heap (con.t) 其結果如下圖所示： 若減少某一鍵值(decrease key)之後，其值還是比parent來得大，則不需調整之。此一減少某鍵值的值之Big-O為O(1) 20 28 22 42 39 2 6 50 31 15 36 12 1 min[H] 37

11.4 Fibonacci heap (con.t) 11.4.4 刪除的動作 刪除的動作： 11.4.4 刪除的動作 刪除的動作： 刪除的節點若為最小值，即和擷取最小值的情況是一樣的，刪除此節點並將其所屬的child node為此棵樹的root，重新連結這些節點，如將圖11.2刪除節點2，則將成為下圖所示 20 28 22 42 39 16 6 31 15 37 12 36 50 min[H]

11.4 Fibonacci heap (con.t) 並重新選擇root中最小值為6，因此min[H]指向此節點，之後再進行合併的動作 若刪除的不是最小值的話，如刪除圖11.2中的16，則成為 20 28 22 42 39 2 6 50 31 15 36 12 37 min[H]

11.4 Fibonacci heap (con.t) 亦即從double circular list中刪除掉，然後將其children node成為root集合中的一員，如刪除16，則37就會成為root集合中的一員，並選擇root集合中最小的一員當其min[H]，之後再進行合併的動作 而此刪除動作的Big-O為O( log n)