Data Structure - Ch3 Priority Queue (Heap)

Chapter 3   Priority Queue (Heap)

3.1  MAX-Heap、min-Heap

• Definition
• 任意節點小於它的所有後裔，最小元素在heap的root上。
• heap總是一棵complete tree。(因此常用array存放)

• Operation
• SearchMin() : Return an element with minimum priority，O(1)。就是root
• Insert() : Insert an element with arbitrary priority，O(log n) 。向上挑戰的概念!

1. 依照complete tree順序，建立一個new empty node
2. bubble up (reheap的上濾) : 將父節點元素轉移至empty node，完成empty node上移，直至滿足heap特性

• DeleteMin() : Delete an element with minimum Priority，O(log n)。向下挑戰的概念!

1. 刪除root  
2. 最後一個元素移動到root  
3. trickle down (reheap的下濾)

• heap的建立
• 方法1 : 每次將每個元素插入之後，邊做向上調整。
• 方法2 : 一次讀入所有的元素放入陣列，從最後一個元素開始對其做向下調整。
• 這兩種方法前者較慢，但可以保證過程中heap皆為合法狀態；後者較快，但是當資料讀完之前，heap還無法使用，因為它還不是一個完整的heap。
• 使用時機 
• heap sort : O(nlogn), Quicksort is generally faster, but Heapsort is better in time-critical applications
• Priority queue最適合的資料結構

3.2   Leftist Tree

• 定義
• A leftist tree (HBLT, height-biased leftist tree) is a binary tree such that if it is not empty, then Shortest(LeftChild(x)) ≥ Shortest(RightChild(x))  
• Shortest()：node[i]到他子孫中最近外節點所經過的邊數
• 增加的external node 為邏輯上的存在

• A max HBLT is an HBLT that is also a max tree. A min HBLT is an HBLT that is also a min tree.
• Meld() operation
• These operations are based on melding two min leftist tree. 
• Insert x into T
• Create a min leftist tree containing a single element 
• meld the two min leftist tree 
• Delete min
• Meld the min leftist trees root− > leftChile and root− > rightChild
• delete the root. 
• Meld()步驟
• 挑出a、b之root的最小值作為新樹之root(令a為最小)。
• A之root為新樹之root，且a之左子樹保留，將a之右子樹與b合併 。
• 重複前兩個步驟，直到合併完成。
• 檢查有無滿足min leftist tree性質，若沒有，則要對調左右子樹來調整。

3.3   Binomial Heap 

• Binomial Tree定義：
• B0 就是一個node 
• B_k 是由兩顆 B_k−1 binomial tree 連結而成(可看成B_1~k-1 binomial tree再加上root組成). 

• Binomial Tree含有下列特性
• B_k 的height為k
• B_k 的Binomial Tree共有2^k個node
• 在第i層有C( k,i )個node，二項式係數(巴斯卡三角形)的概念
• root 擁有Bk 樹最大 degree k
• Binomial Heap 定義
• Binomial Heap 是 mergable heap，由一群 Binomial Tree組成，每個Binomial Tree都滿足 min-heap的性質。
• 對於高度為k的Binomial Tree只能存在最多一棵
• 以二進位來看待的話，第K位就代表是否存在高度為K的BT，因此任何數量的結點都可以用不同的BT給組合出來 (十進制換二進制的概念)
• Binomial Heap 實現
• 採用 Left-Child Right-sibling的方式來實現，左邊指向child,右邊指向同輩
  value: node的值,  degree: 以此node為root的BT的高度,  parent: 指向其parent 

• Operation in Binomial heap
• size()：每個root的degree得到其node數量，再把所有加總即可。
• Traverse()
• mergeHeap()
• 先把兩個 Binomial Heap的 list 給重新串接起來，以degree為key做sorting
• 再根據這個新的Binomial heap list開始進行一系列的合併
• 如果只有兩個高度相同的BT，就直接合併，如果有三個高度相同的BT，就把後面兩棵合併(維持sorting)，因此為O(logn)
• Insert()
• 創建一個新的 Binomial Heap，然後跟原本的Heap執行合併即可，為O(log)
• findMin()
• 由於每個Binomial heap本身都已經是min-heap，因此只要針對每個BT的root比較其值即可。直接比較root而沒a指標直接指最小，因此為O(logn)
• deleteMin()
• find min,        ex : B4(10000) 
• remove root,  ex : B0~3(1111)
• merge,           ex : B_other + B0~3(1111)
• Decreasing a key
• same as the binary heap, bubbling up the node toward the root of the tree, height is O(lg n). 
• Deleting a key
• make the key value to be −∞ then decreasing key. 
• The node goes to the root, then extracting the node with minimum key. 

3.4   Fibonacci Heaps

• 定義：
• Fibonacci Heaps，簡稱為F-Heap，是B-Heap的General型態，所以B-Heap是F-Heap的一種，類似於Binomial heaps也是min tree or max tree組成
• 各層的siblings使用circular doubly linked list
• 新增mark欄位：記錄此點是否曾被刪掉一個點。新建或新成為兒子時設為FALSE。
• Operations
• merge : 把兩個forest直接變成同一個forest, lazy approach 
• lazy approach： 不用把同樣degree的tree merge，和binomial heap不同，O(1) 
• insert：同樣使用lazy approach
• findMin：a指標直接指最小，O(1)
• deleteMin：最終重整，之前的lazy merge都等到這時候才一起merge，除了delete min外，其他都可以”平均”達到O(1)!
• decrease：把某一個element(key)數字減少以後，那個element可能就比他的parent小，必須做一些動作來修正。
• Cascading cut
• 如果減少以後, 比它的parent小, 就把它跟parent中間連結砍斷, 把以該element的subtree移到最上層
• 如果這個parent已經被砍過一次小孩(mark==True), 則把它和它的parent也砍斷, 移到最上層, 並繼續往上檢查是否有此情形… 
• delete：同Binomial tree 

• Potential function
• potential function 的方式來作 amortized analysis
• Φ(H) = t(H) + 2 m(H)
• 其中 t(H) 代表 tree 的個數, m(H)代表marked 點數，下圖的Φ(H) = 5 + 3*2 = 11。 

• Maximum degree D(n) = O(log n) 
• EXTRACT-MIN 與 DELETE 的 amortized cost 都是 O(D(n))
• Delete min —> O(degree(trees)+m) = O(log n + m), m=number of trees in the first level
• Decrease —> O(c), c 為mark為黑色之node個數 (已經被刪掉一個小孩的個數)
• 定理：b為任何Fibonacci heap中的一個node, 則b的degree最多為1.618…, m是以b為root之subtree的node數目

3.5   SMMH (Symmetric Min-Max Heap) 

• 定義
• SMMH 是一棵完全二元樹
• 樹根不存資料
• 若x為SMMH中的某個node，令 S(x)是以 x 為樹根的子樹中，除了節點 x 以外的其他節點集合，則下面兩條件成立：
• x 的 left child Lchild(x) 是 S(x)中最小的元素
• x 的 right child Rchild(x) 是 S(x)中最大的元素

• Operation
• Insertion()

1. 將complete binary tree的node增加一個，置入插入的資料 x。 
2. 若 x 有 left sibling y且 y > x，則將y與x對調。  
3. bubble-up pass，以gp(x)代表 x 的grand parent
4. 重複3直到沒有 (a) 或 (b) 情況為止。 

• 範例:Insert 3 的例子 

• DeletionMin()
• 將 h[2] 取出，由 h[n+1] 取出為 x 置於h[2]，令節點個數 n 減少 1。 
• x若 y>x，則結束處理。 
• 若 y<x，則將 y 與 x 交換，繼續 2。 
• 若x已無 child 而有 left sibling z，若 z>x，則將x與z交換，然後結束處理。