CH 9 Heap

Min-Max heap

Definition

• A mix-max heap is a complete binary tree such that if it is not empty, each element has a field called key.

• Alternating levels of this tree are min levels and max levels, respectively.

• Let x be any node in a min-max heap. If x is on a min (max) level then the element in x has the minimum (maximum) key from among all elements in the subtree with root x. We call this node a min (max) node.

• example

• 樹中為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)

Insertion of Min-Max heap

• Step 1
  • 將欲新增的元素插入 Min-Max Heap 最後一個節點
• Step 2
  • 將新增節點與其父節點做比較，若父節點位於 Min (Max) Level，且新增節點小於 (大於) 父節點，則交換二者的位置。
• Step 3
  • 若交換後新增節點的位於 Min (Max) Level，則依序往上與各 Min (Max) Level 的節點比較，若新增節點較小(大)，則二者交換。
• Step 4
  • 重複 Step 3，直至不能再交換或到 root 為止。

Deletion of Min-Max heap

Delete Min

1. Step1: 移走 root 資料
2. Step2: 將 heap 的 last-node X 插入 step1 後的 heap 中
   • Case1 : Root 沒有任何 child :
     X 插入 root 位置
   • Case2 : Root 只有 children 沒有 grandchild
     令 children 中最小值為 k
     若 k < X 則將 X 與 k 互換位置
     否則將 X 插入 root 位置
   • Case3 : Root 有 grandchildren
     令 grandchildren 中最小值為 k 且 k 之 parent 為 p
     若 k < X 則
     K 移到 X 的位子
     若 X > p 則 X 與 p 的值互換
     重複 step2
     否則將 X 插入 root 位置

• Example
  • Start
  • Result

1. Step1: 若只有一個 node 則移走 root , 結束
   否則移走 root 之 children 之最大者,進行 step2

2. Step2: 將 heap 的 last-node X 插入 step1 後的 heap 空位中(並視為Root)

   • Case1 : 此位置沒有任何 child :
     X 插入此位置

   • Case2 :此位置只有 children 沒有 grandchild
     令 children 中最大值為 k
     若 k > X 則將 X 與 k 互換位置
     否則將 X 插入 root 位置

   • Case3 :此位置有 grandchildren
     令 grandchildren 中最大值為 k 且 k 之 parent 為 p
     若 k > X 則
     K 移到 X 的位子
     若 X < p 則 X 與 p 的值互換
     重複 step2
     否則將 X 插入 root 位置

• Example
  • Start!
  • Result

練習

• (a) Insert 8, 16, 33, 46,61, 5, 13 (b) Delete-Min, Delete-Max, Delete-Max, Delete-Max, Delete-Max, Delete-Max,
  

[如果有錯誤，請在留言中告知網址]

考題

99年　考Min-Max heap 定義

Deap

• Definition: A deap is a complete binary tree that is either
  empty or satisfies the following properties:

1. The root contains no element
2. The left subtree is a min heap
3. The right subtree is a max heap
4. If the right subtree is not empty, then let i be any node in the left subtree. Let j be the corresponding node in the right subtree. If such a j does not exist, then let j be the node in the right subtree that corresponds to the parent of i. The key in node i is less than or equal to that of j (i.e. i.key <= j.key)
   

對應點

• If i is a node in the min heap of the deap, its corresponding node in the max heap is j
• j is defined in property (4) of definition is given by
• $j=i+2^{\lfloor lo{g}_{2}i\rfloor -1}$
• $if(j<n+1)j/=2$ (如果對應點不存在，對應點位原對應點的Parent)

Deap insert

• Deap 的加入動作與其它堆積樹一樣，將新的鍵值加入於整棵樹的最後，再調整至符合堆積樹的定義
• 假設已存在一 Deap 如下
  
• 若加入25，加入後右子樹仍為一棵max-heap，如下所示，且左子樹對應節點15小於等於它所對應的右子樹節點25，符合deap的定義
  
• 加入17，加入後的圖形如下所示
  
• 此時右子樹仍為max-heap，但17小於其左子樹的對應節點20，故將17與20交換
  
• 加入40，如下所示
  
• 加入後左子樹雖為min-heap，但40大於其對應節點25(與節點40的父節點對應之右子樹節點)，不符合deap的定義，故將40與25交換，如下所示：
  
• 交換後樹中的右子樹不是一棵max-heap，重新將其調整為max-heap即可
  

---

• 額外範例
  
• 加入４之後
  
• 加入30之後
  

Deap deletion

Delete Min

• Suppose we want to remove the minimum element from the deap

1. We first place the last element into a temporary element t.
2. Vacancy created by the deletion of the min element is filled by moving from position 2 to a leaf
3. Each move is preceded by a step that moves the smaller of the elements in the children of the current node up
4. Then move to the position previously occupied by the moved element
5. Repeat the process until we move the empty node to a leaf position
6. Compare the key put in the temporary element with the max partner
7. If <, no exchange is needed. The temporary element is inserted into the empty leaf node
8. If >, exchange them
   

練習

• (a). Insert 4, 80, 52, 11 (b) Delete-min, Delete-min, Delete-max, Delete-max
  

考題

• 99年
  
  
  
  

[如果有錯誤，請在留言中告知]

Leftist Trees

• Leftist trees are defined using the concept of an extended binary tree. An extended binary tree is a binary tree in which all empty binary subtrees have been replaced by a square node
• The square nodes in an extended binary tree are called external nodes. The original nodes of the binary tree are called internal nodes

Shortest(x)

• Let x be a node in an extended binary tree. Let LeftChild(x) and RightChild(x), respectively, denote the left and right children of the internal node x
• Define shortest(x) to be the length of a shortest path from x to an external node. It is easy to see that shortest(x) satisfies the following recurrence:
  
  
  
  

Definition

• A leftist tree is a binary tree such that if it is not empty, then shortest(LeftChild(x)) ≥ shortest(RightChild(x)) for every internal node x
• Lemma: Let x be the root of a leftist tree that has n (internal) nodes
  • (a) n ≥ 2shortest(x) – 1
  • (b) The rightmost root to external node path is the shortest root to external node path. Its length is shortest(x).

Min (Max) Leftist tree

• Definition: A min leftist tree (max leftist tree) is a leftist tree in which the key value in each node is no larger (smaller) than the key values in its children (if any). In other words, a min (max) leftist tree is a leftist tree that is also a min (max) tree

Operations

• Like any other tree structures, the popular operations on the min (max) leftist trees are insert, delete, and combine
• The insert and delete-min operations can both be done by using the combine operation
  1. To insert an element x into a min leftist tree, we first create a min leftist tree that contains the single element x. Then we combine the two min leftist trees
  2. To delete the min element from a nonempty min leftist tree, we combine the min leftist trees root->LeftChild and root->RightChild and delete the node root.
  3. To combine two leftist trees:
     1. a new binary tree containing all elements in both trees is obtained by following the rightmost paths in one or both trees
     2. Next, the left and right subtrees of nodes are interchanged as necessary to convert this binary tree into a leftist tree
• The complexity of combining two leftist trees is O(log n)

Combine

• 挑出a、b之root的最小值作為新樹之root(令a為最小)
• A之root為新樹之root，且a之左子樹保留，將a之右子樹與b合併
• 重複前兩個步驟，直到合併完成。
• 檢查有無滿足min leftist tree性質，若沒有，則要對調左右子樹來調整
  
  
  
  

Exercise

• combine
  
  
• answer
• 

考題

• 99年
• Definition
• combine
  
  

[有錯誤請告知]

Binomial tree

• Binomial tree Bk is an ordered tree defined recursively.
  
  
• Bk is degree k binomial tree.
  
  
• Bk , k > 0, is:
  
  
• Lemma (Properties of binomial trees)
• For each binomial tree Bk
  • There are 2k nodes
  • The height of the tree is k
  • There are exactly k! / i!(k-i)! nodes at depth i
  • The root has degree k, which is greater than that of any other node
    Theorem: The height of Bk , the binomial tree of order k, is k
    Theorem: The number of nodes at level l in , the binomial tree of order k, where 0≦ l ≦ k , is given by the binomial coefficient C ｋ取ｌ

Number of Nodes in Bk

• Nk = number of nodes in Bk.
• N0 = 1
  
  
• Bk , k > 0, is:
  
  
• Nk = N0 + N1 + N2 + …+ 1 = 2k.

Equivalent Definition

• Bk , k > 0, is two Bk-1s.
• One of these is a subtree of the other.
  
  
  N0 = 1
  Nk = 2N(k-1) = 2^k.
  If we start with zero elements and perform operations as described, then all trees in all binomial heaps are binomial trees.
  So, MaxDegree = O(log n).
  
  
  
  

Binomial heap(B-heap)

Definition

• Node: degree, child ,left_link, right_link, data, parent
• roots are doubly linked
• a points to smallest root
• B0 has exactly one node
• Bk, k > 0, consists of a root with degree k and whose subtrees are B0, B1, …, Bk-1
• Bk has exactly 2k nodes
  
  
  
  

Operations

Insert

• Insertion Into a Binomial Heap
  • make a new node into doubly linked circular list pointed at by a
  • set a to the root with smallest key

Combine

• Combine two B-heaps a and b
  • combine two doubly linked circular lists to one
  • set a to the root with smallest key

Delete

• 一般刪除的動作乃是擷取此棵Binomial heap的最小值出來，因此只要從head[H]指向的鏈結串列中就可找到最小的值在那一棵Binomial tree，此時將此節點刪除之即可

Cost

• insert and combine is O(1), and that of each delete-min operation is O(log n)

What’s BH&FH – Definition( Important)

• A binomial heap is a collection of binomial trees.
• The binomial tree Bk is an ordered tree defined recursively. The binomial tree B0 consists of a single node. The binomial tree Bk consists of two binomial trees Bk-1 that are linked together: the root of one is the leftmost child of the root of the other.
• Like a binomial heap, a Fibonacci heap is a collection of min-heap-ordered trees. The trees in a Fibonacci heap are not constrained to be binomial trees.
• Binomial heap is a special case Fibonacci heap
• Binomial heap node: data, link, degree and child
• Fibonacci heap node: data, parent, childcut, child, link and degree.

考題

99年

Fibonacci Heaps(F-heaps)

Definition

• A Fibonacci heap is a data structure that supports the three binomial heap operations: insert, delete-min (or delete-max),and combine, as well as the following additional operations:
  • (1) decrease key: Decrease the key of a specified node by a given positive amount
  • (2) delete: Delete the element in a specified node
  • this two operations are followed by cascading cut
• Two varieties of Fibonacci heaps:
  • Min Fibonacci heap: is a collection of min trees
  • Max Fibonacci heap: is a collection of max trees
• B-heaps are a special case of F-heaps.
  
  

Operations

Delete

• Follow the below steps to delete a node b from an F-heap:
  • If min = b, then do a delete-min; otherwise do Steps 2, 3, and 4 below
  • Delete b from its doubly linked list
  • Combine the doubly linked list of b’s children with the doubly linked list pointed at by min into a single doubly linked list. Trees of equal degree are not joined as in a delete-min operation
  • Dispose of node b
• Example: delete 12
  
  
  
  

Decrease Key

• To decrease the key in node b, do the following:
  • (1) Reduce the key in b
  • (2) If b is not a min tree root and its key is smaller than that in its parent, then delete b from its doubly linked list and insert it into the doubly linked list of min tree roots
  • (3) Change min to point to b if the key in b is smaller than that in min.
    
    

Cascading cut

• whenever a delete or decrease-key operation deletes a node q that is not a min tree root from its doubly linked list, then the cascading cut step is invoked
• If two children of x were deleted, then x must be cut and moved to the ring of roots.(Important)

Extract Min

考題

99

Below figure is a Fabonacci heap on 10 keys, Note that it consists of two trees. If we apply the following sequence of 4???(老師算術不太好) operations:

• delete-minimum
• insert 15
• delete 44
• decrease 72 to 13
• delete 63

What will be the resulting Fibonocci heap for each operation?

[誰會啊???有人能確認答案嗎?]

ch10

Optimal binary search tree

Path length

• External(E):Sum over all external nodes of the lengths of the paths from the root to those nodes.
• Internal(I): Sum over all internal nodes of the lengths of the paths from the root to those nodes.
• Binary trees with maximum E also have maximum I. E=I+2n
• For all binary trees with n internal nodes
  • $MaximumI=\sum _{i=0}^{n-1}i=n(n-1)/2(skewtree)$
  • $MinimumI=\sum _{1\le i\le n}^{}\lfloor lo{g}_{2}i\rfloor (completebinarytree)$

Cost

Example

CODE

考題

M way search tree

• 節點的型態是n, A0, (K1, A1), (K2, A2),…,(Kn, An) 其中Ai是子樹的指標 0 ≤ i ≤ n < m; n為節點上的鍵值數，Ki是鍵值1 ≤ i ≤ n < m。
  
  
  
  

Maximum pairs

• For 'm' way and height of 'h'
• Maximum number of nodes =
  $1+m+m^2+m^3...m^{h-1}=m^h-1/(m-1)$
• Each node has
  $m–1$ pairs.
• Maximum number of pairs =
  $m^h-1$
• 2-3 tree: m = 3
• 2-3-4 tree: m = 4

2-3 tree

Definition

• 何謂2-3 Tree？
• 2-3 Tree 可以是空集合；
  • 若不是空集合，則要符合下列的定義
  • 2-3 Tree中的節點可以存放一筆或兩筆資料。
  • 若節點中存放了一筆資料Ldata，其必須存在兩個子節點 – 左子節點與中子節點。假設資料Ldata的鍵值為Ldata.key。
  • 若節點中存放了兩筆資料Ldata與Rdata，則會存在三個子節點 – 左子節點、中子節點與右子節點
• 若節點中存放了兩筆資料Ldata與Rdata，則會存在三個子節點 – 左子節點、中子節點與右子節點。假設資料Ldata與Rdata的鍵值分別為Ldata.key與Rdata.key，則:
  • Ldata.key < Rdata.key
  • 左子節點所存放的資料鍵值必須小於Ldata.key
  • 中子節點所存放的資料鍵值必須大於Ldata.key，小於data.key
  • 右子節點所存放的資料鍵值必須大於Rdata.key

Insertion

• 從2-3 Tree的開始搜尋，假使加入的資料其鍵值在2-3 Tree中找不到(不可有相同的節點資料存在同一個2-3 Tree中)，則加入2-3 Tree中。
  • 假設加入的節點，該節點只有一筆資料，則直接加入；
  • 該節點已存在兩筆資料，加入後不符合2-3 tree的定義，因此必須將此節點資料一分為二，分別放入最大鍵值和最小鍵值並將中間的鍵值，往上放到父節點。
  • 該節點的父節點也已有二筆資料，先將該節點一分為二，並將中間資料往上提及父節點，接著重覆此步驟來調整父節點，直到符合2-3 tree為止
    
    
    
    

Deletion

• Tree的刪除分成兩部份：
  • 一為刪除的鍵值是在樹葉節點上（leaf node）
  • 二為刪除的鍵值是在非樹葉節點（non-leaf node）
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

考題

2-3-4 tree

B tree

Definition

• 2-3 tree is B-tree of order 3.
• 2-3-4 tree is B-tree of order 4.

number of nodes

• Maximum number of nodes =
  $1+m+m^2+m^3...m^{h-1}=m^h-1/(m-1)$
• Minimum number of nodes =
  $2\times \lceil m/2{\rceil }^{h-1}$

number of keys

• maximum number of keys =
  $m^h-1$
• Minimum number of keys =
  $2\times \lceil m/2{\rceil }^{h-1}-1$

考試重點

CH 9

• Min-Max
  • Def
  • Insert
  • Delete Min Max
• Deaps
  • Definition
  • Insert
  • Delete
• Leftist
  • Definition
  • shortest
  • Combine
• Binomial
  • tree Definition
  • heap
• Fibonacci
  • 和Binomial的差異
  • Delete
  • Reduction
  • extract min

CH 10

• Binary search tree(一定考)
  • 程式(pseudo code)
  • 圖
• B-tree
  • Definition
  • children key數 order
  • delete 補位方向
• 2-3 tree degree
  • Insert
  • delete
• 2-3-4 degree
  • key數
• M-WAY
  • 資料結構表示
  • key 數

tags: CSnote