前言
資料結構中有很多種基本的樹，像是heap就是其中一種，可以作為priority queue做使用。但heap的權重只提供單向，無法提供雙向權重。因此，人們開始想有沒有方法可以實現「Double-ended」，也就是既可以選出權重最小，亦可挑出權重最大的物件。
目前大學中最常見的double-ended priority queue有兩種：Min-Max Heap與Deap。
本篇會先介紹這些進階樹，介紹它們是如何實現「雙端點權重」的操作，像是insert與delete。
Min-Max Heap
定義
- Complete Binary Tree (不解釋)
- Tree level被分為
min level和max level - 若某節點位於min(max) level，則以該點為根的子樹中，他的權重為最小(大)值。
- 第一層(root)必須為
min level
看完這些定義後，是不是心裡覺得後面兩點到底在幹嘛？放心，我一開始也不懂這些操作有什麼意義。
仔細想一下第三點的意思，假設某一層(X)是min-level，則他下下層(Y)就一樣是min-level，對吧？那麼，依據後段所述「以該點為根的子樹中，他的權重為最小值」，我們可以知道X層的節點都會比他下面的每個min-level都還要小，也就是min-level的權重越往下越大。同理，max-level的權重則是越往下越小。
這樣的話我們可以知道Min-Max Heap的一些特性：
1. 最小值位於root
2. 最大值位於第二層，兩個節點中某一個
3. 越下層的min-level會越大；越下層的max-level會越小
範例
1. 插入 (insert)
- 步驟一：令X為新進節點，將X放置在最後節點的後面一位(維持complete)
- 步驟二：假設P為X的父點，則分成兩個case
(1)P位於min-level，則：
if(X.key < H[P].key) {
H[n] = H[P]
VerifyMin(H, P, X)
}
else
VerifyMax(H, n, X)
(2)P位於max-level，則：
if(X.key > H[P].key) {
H[n] = H[P]
VerifyMax(H, P, X)
}
else
VerifyMin(H, n, X)註：
(1) H指存放min-max heap的array
(2) P, n代表索引，這裡從1開始算
關於這兩個case，讀者會發現裡面的程式碼是差不多的，可說兩者是一體兩面。以第一種情況來說，當X的權重比他的父點還大，那麼我們接下來只需要調整min-level的節點；反之，我們只需要調整max-level的節點。而原因下面晚點會說明，讀者就先記著這些規則。
來個小小範例
看完上面的範例後，來講解一下為什麼只需要驗證min-level或max-level其中一個即可。
以一個leaf而言，往上不斷把各個祖先擷取下來，會形成一條串列，如下：
從最前面推導的性質，我們可以得到一個結論：n2 > n4 > n5 > n3 > n1。
現在假設n6位在max-level而且小於n5，依照上面的規則，我們將他們互換，使n5轉移到max-level。以原先的結論，對於max-level而言，這次的互換並沒有造成改動，大小順序依然是n2 > n4 > n5，依舊滿足Min-Max Heap的條件。至於min-level，因為我們只知道 n5 > n6，所以必須要讓n6去挑戰上面的min-level節點，也就是VerifyMin。因此，當順利將所有min-level節點調整完畢時，整棵樹就也調整完成。
而若n6 > n5時，處在min-level的節點則完全不須移動，因為所有max-level的節點都大於任何一個min-level的節點。我們反而需要另外對max-level做調整，畢竟我們不清楚n6對於n2和n4的大小關係，所以必須做VerifyMax以滿足Min-Max Heap的條件。
上述是「若新的節點被放置在max-level」的情況，至於當節點被置於min-level時，整個比較關係會反過來。這邊就不多做討論了，由讀者慢慢去演練與感受吧~
2. 刪除最小值 (delete min)
- 步驟一：移走root(即所求)，將最後一個節點(令為X)拉至root的空位
- 步驟二：考慮以下三種case
<case1>: root無子點，直接 -> Exit
<case2>: root無孫點，則找出子點中最小節點。若比root還小則兩者交換 -> Exit<case3>: root有孫點，且令最小孫點C，且C之父點為P。接著考慮以下狀況：
if(X.key > C.key) {
X, C 互換
if(X.key > P.key) X, P 互換 回到步驟二(recursive call)
}
-> Exit
第一和第二種狀況我想不需要多說，算是trivial case。至於第三個情形，因為Min-Max Heap的特性就是min-level的權重是遞減的，所以第二小的節點必定在第三層(也就是第二個min-level)。因此，若C的權重比X小，代表現在整棵樹中的最小值就是它，所以要互換。在此之下，若X比P的權重大，因P原本在以自己為根所形成的子樹中是最大值，但X現在比P還更大，所以將X與P互換。最後，繼續往下遞迴直到結束。
一樣來個小小範例
至於刪除最大值的操作就類似，只是要先從第二層的節點中找出真正的最大值，以其為根做上述的操作，並且在每個步驟中，將if裡面的大於換成小於，找最小值換成找最大值即可。
Deap
定義
- 一棵Complete Binary Tree
- root不儲存任何資料
- root的左子樹是
min-heap; 右子樹則為max-heap - 在root左子上的任一點 i，令 j 為他在右子樹中對應的節點，i 點的權重必須小於 j 點的權重。
(p.s 若無對應點則取其父點)
Deap的意思就是取自Double-ended Heap，root的兩棵子樹分別成為一種heap。若先不論細節，從直覺上我們會猜整棵樹中的最小值來自於root的左子，而最大值就來自於root的右子。
至於原因，眼尖的讀者看到第四點時，應該馬上注意到它的用意了。是的！因為左子樹是一棵min-heap，所以root的左子必定是該子樹中最小的；而對於右子樹也是，root的右子必定是其子樹中的最大值。
看到這你是不是覺得阿所以勒呢，不就一般Heap的性質？當然說的沒錯，但重點還在後面。加入的第四點告訴我們左右樹的對應點必須有大小順序，也就是說右子樹的最底層整體會大於左子樹的最底層。
因此，root的左子會小於該子樹最底層的所有節點，這些底層的節點又小於他們的對應點，而root的右子則會順勢大於那些對應點。綜合以上，我們會發現整棵樹的最小值真的是root的左子，最大值則真的也是root的右子。
範例
1. 插入(insert X)
這裡的插入節點並不包括刪除最小/大的相關操作。因為刪除節點也會需要涉及到插入的步驟，雖然步驟幾乎相同，但這裡討論的前提是不包含正在做刪除，只是單純新增節點而已。
- 步驟一：將X放在最後節點的下一位
- 步驟二：以X的位置分成兩個case討論
(a) 在Min Heap→右側必無對應點，由父點代替
(b) 在Max Heap→左側必有對應點
(1) X在 Min Heap
if(X.key > Deap[j].key) {
Deap[n] = Deap[j];
VerifyMax(Deap, j, X);
}
else
VerifyMin(Deap, n, X);(2) X在 Max Heap
if(X.key < Deap[j].key) {
Deap[n] = Deap[j];
VerifyMin(Deap, j, X);
}
else
VerifyMax(Deap, n, X);
- 範例
Deap的交換後調整與前面的Min-Max Heap非常類似，討論也是幾乎一模一樣，但我還是稍微帶一下觀念。
首先以X在Min Heap為前提，令X的父點為P而對應點為Y。依據Deap的性質，可以知道P的權重小於Y。假設X的權重大於Y，此時會違反Deap的條件，所以我們將他們互換過來。在交換後，Y的權重依舊大於P，所以不會對Min Heap這端造成任何影響，反倒是Max Heap那端要檢驗是否需要調整。
而若X的權重小於Y，因為不知道與父點的大小關係，我們就必須去調整Min Heap。
2. 刪除最小值(delete min)
- 步驟一：移走root的左子，將最後一個節點移出並存在X中
- 步驟二：對於缺少root的左子樹，將較小的子點移上去替補，並以此類推，使最後在leaf會有一個空缺。
- 步驟三：對該空格執行Insert X
- 範例：
刪除最小值(或是最大值)分成兩個步驟：遞補與再插入。
首先，遞補的目的是不影響Deap的第三性質的情況下，同時滿足heap的性質，也就是維持min heap或是max heap。
假設有一個準備往上替補的節點令作X(位於min heap)，因為他的父點會比他小，而且他的對應點Y本身也是小於其父點P(若無實質對應點則Y與P是同一點)，所以X的權重自然就會小於P點，因此上移並不影響Deap的第三性質。
第二，經過一連串的遞補程序，會在leaf產生一個空缺，此時就會需要將最後一個節點插入至該空缺。前面的插入(insert)有提到一個前提是「未進行刪除」，這個前提的存在與否其實對步驟並無影響，兩者的程序是一模一樣的。那為什麼要特地設定這個前提呢？這就會牽扯到上一步的遞補所產生的後果。
想一下，遞補挑選的對象是從子點中選一個較小的節點補上去。所以事實是我們並不能確定最後出現的空缺在哪裡，有可能這個空缺沒有對應點，也可能剛好有，一般我們是無法預測的。因此，若該空缺有對應點而且位於min heap上，這時就跟一般插入不同。
那如果上述的情形發生，為什麼不會影響插入的步驟呢？我們先來看下面這張圖：(假設是delete min)
若X < C2，因為符合第三性質，所以只須考慮是否符合min heap。除此之外，本身C1就小於C2、P1 < P2，儘管它們被X換下來也不必擔心影響第三性質，因此並不影響。
而若X > C2，我們試著將他們互換，使得C2轉移到上圖的灰色節點中。同樣地，已知P1 < C1 < C2 < P2，所以當C2成為C1的子點時，仍然滿足min heap的條件，只剩下max heap需要調整。因為即便X將上層的節點換下來，對於左側的min heap而言也只會把權重更大的節點拉下來，並不會導致第三性質遭到破壞，所以可以安心做調整。
至於「刪除最小值且無對應點」或是「執行刪除最大值」的討論，就留給讀者去思考，大抵上的討論過程是一樣的。
總之，綜合以上的討論，我們會發現再插入的步驟可以直接取用一般插入的方式。
複雜度
看完上面超級冗長的解釋，大家的小腦袋應該已經爆炸了，就算不是第一次看，也會覺得很燒腦。儘管如此，我們還有最後一步要走完。
一個資料結構重要的不只是它的功能性，也包含可以多快完成每一個操作，所以接下來會討論Min-Max Heap與Deap各個操作的複雜度。
Min-Max Heap
- Insert
⭐ 與父點討論是否交換：O(1)
⭐ 調整min-level或是max-level：O(h), h = log(n)為樹高
— 總和：O(log n) - Delete (以case 3做討論)
⭐ 從孫點中找到最小/大值：O(1), 需要最多3次比較
⭐ 針對P, C討論是否互換：O(1), 需要最多2次比較
以上步驟最多執行h/2次
— 總和：O(log n) - Find Min/Max
⭐ 最小值在root：O(1)
⭐ 最大值從root的子點挑一個：O(1)
— 總和：都是O(1)
Deap
- Insert
⭐ 與對應點比較：O(1)
⭐ 調整min heap或max heap：O(log n)
— 總和：O(log n) - Delete
⭐ 遞補：O(log n)
⭐ 再插入：O(log n)
— 總和：O(log n) - Find Min/Max
⭐ 最小值在root的左子：O(1)
⭐ 最大值在root的右子：O(1)
— 總和：均為O(1)
結語
Double-ended Priority Queue是一個可以同時選出最小或最大權重節點的樹，其中以Min-Max Heap與Deap最為人知。當然，除了這兩種以外，還有一種Heap也支援雙輸出，叫做SMMH(symmetric min-max heap)。但若加上SMMH的討論，整體篇幅會過於冗長且乏味(本來好像就乏味)，因為它的概念比起前兩者稍稍特別一點，所以我會直接放在延伸閱讀給讀者自行參閱。
會寫這篇文的原因有兩個，一個是因為網路上蠻少有中文版的教學，所以想做給那些需要中文教材的同學，能更快了解各個步驟在做什麼；另一方面是我想把我在考研時所讀的一些知識記錄下來，並不是考完就將手寫的筆記丟置一旁長灰塵。而且若我有一天需要複習且手邊沒有紙本，我可以直接回來看我自己寫的文章。
最後，如果看完覺得對你有很大的幫助，也請分享給其他人吧~
