Over view on Heaps Operation Binary heap Binomial Fibonacci 第13讲: Binomial& Fibonacci Creation Insert e(gn) o(g n) Heaps O(g n) 清华大学 Extract-min o(g n) o(gn) 宋斌恒 O(n) O(g n) Decrease-key e(g n) e(g n) Delete O(g n e(g n) O(g n) 请华大学宋恒 Over view Comparison of the heaps Mergeable heaps support the following 7 If not support the operation union than the operations binary heap is better than binomial heap 1. Create heap 2. Insert Fibonacci heap is totally better than 3. Minimum binomial heap with supporting the merging 4. Extract-min operation in the amortized sense 5. Union 6. Decrease-key 7. Delete 清华大学末斌恒 请华大学宋恒 Common issues Binomial trees It is inefficient to support the operation of Binomial trees B, are defined reclusively as search for all kinds of the heaps, so it needs Bo consists of a single node to visit the elements by its handle or the The B consists of two Bk- that are linked pointer gether the root of one Bk- is the left most child of another one B I 清华大学末破恒 请华大学宋
1 第13讲：Binomial & Fibonacci Heaps 清华大学 宋斌恒 清华大学 宋斌恒 2 Over view on Heaps Delete Θ(lg n) Θ(lg n) Ο(lg n) Decrease-key Θ(lg n) Θ(lg n) Θ(1) Union Θ( n) Ο(lg n) Θ(1) Extract-min Θ(lg n) Θ(lg n) Ο(lg n) Minimum Θ(1) Ο(lg n) Θ(1) Insert Θ(lg n) Ο(lg n) Θ(1) Creation Θ(1) Θ(1) Θ(1) Fibonacci heap Binomial heap Operation Binary heap 清华大学 宋斌恒 3 Over view • Mergeable heaps support the following 7 operations. 1. Create heap 2. Insert 3. Minimum 4. Extract-min 5. Union 6. Decrease-key 7. Delete 清华大学 宋斌恒 4 Comparison of the heaps • If not support the operation union than the binary heap is better than binomial heap • Fibonacci heap is totally better than binomial heap with supporting the merging operation in the amortized sense 清华大学 宋斌恒 5 Common issues • It is inefficient to support the operation of search for all kinds of the heaps, so it needs to visit the elements by its handle or the pointer 清华大学 宋斌恒 6 Binomial trees • Binomial trees Bk are defined reclusively as – B0 consists of a single node – The Bk consists of two Bk-1 that are linked together: the root of one Bk-1 is the left most child of another one Bk-1
22 O-3个 清华大学宋域恒 请华大学宋斌 Properties Proof of the properties For binomial tree B: All by induction, because it is defined 1. There are 2k nodes recursively. Here we omit the proof. 2. The height of the tree is k 3. There are exactly (,)nodes at depth i for i=0, 1, 2,- k ·课堂练习 4. The root has degree k, which is greater than that of any other node; moreover if the children of the root e numbered from left to right by k-1, k-2,--, 2, 1,0, 清华大学末斌恒 请华大学宋恒 第三条性质的证明 Binomial heaps a binomial heaps H is a set of binomial D(k,i)=D(k-1,)+D(k-1,i-1) trees that satisfies the following binomial- heap properties Min-heap property: each tree in H obey the in-heap property, which means that the key of each node is great than or equal to its parent or any k there exists at most one Bk in H. 清华大学末破恒 请华大学宋
2 清华大学 宋斌恒 7 B0 B1 B2 B3 0 1 2 3 Depth 清华大学 宋斌恒 8 清华大学 宋斌恒 9 Properties • For binomial tree Bk: 1. There are 2k nodes. 2. The height of the tree is k 3. There are exactly (k i ) nodes at depth i for i=0,1,2,…,k 4. The root has degree k, which is greater than that of any other node; moreover if the children of the root are numbered from left to right by k-1,k-2,…,2,1,0, child i is the root of subtree Bi . 清华大学 宋斌恒 10 Proof of the properties • All by induction, because it is defined recursively. Here we omit the proof. • 课堂练习 清华大学 宋斌恒 11 第三条性质的证明 清华大学 宋斌恒 12 Binomial heaps • A binomial heaps H is a set of binomial trees that satisfies the following binomialheap properties: – Min-heap property: each tree in H obey the min-heap property, which means that the key of each node is great than or equal to its parent key – For any k there exists at most one Bk in H
二项式堆 嚷单罪围 degree Right sibling I Left-child 节点数据 清华大学末域恒 关于右兄弟的法则等 Operations on binomial heap 如果一个节点是其父节点的最右边的孩 1. Creating a new empty binomial heap 子,则该节点没有右兄弟,否则其右兄 弟为其父节点的比自己靠右的下一个孩 2. Minimum ·如果是根节点,其父节点为 ·孩子节点指向其最左孩子,否则为空 L. Ifkey(xmin then minekeyIxh yex 清华大学末斌恒 请华大学宋恒 Uniting two binomial heaps 合并步骤 两个相同阶数的二项式树的联结 第一步:融合,按照树的大小从小到大 Binomial-link(y, z) 排列两个堆的所有二项式树 1. Parently]ez ·第二步:从小到大联结相同的二项式 2. Siblingly]child[z] 树:如果当前大小相同的树连续只有 3. Child[z]ey 个跳过,只有两个联结,只有三个则联 4. Degree[z]degree[ z+ 结后两个,然后继续 清华大学末域恒 请华大学宋
3 清华大学 宋斌恒 13 Head[H] Key value degree parent Right sibling Left-child 节点数据 结构 清华大学 宋斌恒 14 清华大学 宋斌恒 15 关于右兄弟的法则等 • 如果一个节点是其父节点的最右边的孩 子，则该节点没有右兄弟，否则其右兄 弟为其父节点的比自己靠右的下一个孩 子。 • 如果是根节点，其父节点为空。 • 孩子节点指向其最左孩子，否则为空 清华大学 宋斌恒 16 Operations on binomial heap • 1. Creating a new empty binomial heap: head[H]Ånull • 2. H.minimum 1. yÅnull 2. xÅhead[h] 3. minÅinfinity 4. While x != null 1. If key[x]<min then minÅkey[x], yÅx 2. xÅsibling[x] 5. return y 清华大学 宋斌恒 17 Uniting two binomial heaps • 两个相同阶数的二项式树的联结 • Binomial-link(y,z) 1. Parent[y]Åz 2. Sibling[y]Åchild[z] 3. Child[z]Åy 4. Degree[z]=degree[z]+1 清华大学 宋斌恒 18 合并步骤 • 第一步：融合，按照树的大小从小到大 排列两个堆的所有二项式树 • 第二步：从小到大联结相同的二项式 树：如果当前大小相同的树连续只有一 个跳过，只有两个联结，只有三个则联 结后两个，然后继续
O② 十」 ○ 合并 清华大学宋域恒 请华大学宋恒 ead[ Head(H 第一步 第二步 清华大学末斌恒 请华大学宋域恒 ead[ ○ 第三步,完成 Insert a node can be transferred to the case of union 清华大学末破恒 请华大学宋
4 清华大学 宋斌恒 19 1 3 5 Head[H] 2 4 6 Head[H] + 清华大学 宋斌恒 20 1 3 6 Head[H] 2 4 5 合并 清华大学 宋斌恒 21 1 3 6 Head[H] 2 4 5 第一步 清华大学 宋斌恒 22 1 4 6 Head[H] 2 3 5 第二步 清华大学 宋斌恒 23 1 4 5 Head[H] 2 3 6 第三步，完成 清华大学 宋斌恒 24 1 4 5 Head[H] 2 3 6 Insert a node can be transferred to the case of union x
OOOOOOOO OOOOOOOO 个堆,合并 Extracting minimum Decrease key red to value 7 清华大学宋域恒 请华大学宋恒 ead[ 二项式堆小结 ·结构:二项式树集合 ·运算:综合效率较好 Deleting key red: decrease to infinity, then extract-min 清华大学末斌恒 请华大学宋恒 完全表示方式 露邈 节点数据 marked 清华大学末破恒 请华大学宋
5 清华大学 宋斌恒 25 9 4 5 Head[H] 20 3 6 Extracting minimum Will be removed 一个堆，合并 清华大学 宋斌恒 26 1 4 5 Head[H] 2 3 6 12 9 Decrease key red to value 7 清华大学 宋斌恒 27 1 4 5 Head[H] 2 3 6 12 9 Deleting key red: decrease to -infinity, then extract-min 清华大学 宋斌恒 28 二项式堆小结 • 结构：二项式树集合 • 运算：综合效率较好 清华大学 宋斌恒 29 Fibonacci heap 24 45 30 32 28 min[H} 90 40 44 29 7 19 6 12 4 22 17 Key value degree parent Right sibling any-child 节点数据 left sibling 结构 marked n[H} 清华大学 宋斌恒 30 完全表示方式
Fibonacci heap的势函数 Decrease 40 to 13: step Potential function number of roots +2 number of marked nodes 清华大学宋域恒 请华大学宋恒 Decrease 40 to 13: step2 46减少为15 ① ⑩ 如果134手m则改变> 清华大学末斌恒 请华大学宋恒 把b)的35降为5 合并:H1和H2 的一众“Q 画每● @@@@睡 e0的9Q ④④ 清华大学末破恒 请华大学宋 6
6 清华大学 宋斌恒 31 Fibonacci heap的势函数 • Potential function = number of roots +2 * number of marked nodes 清华大学 宋斌恒 32 Decrease 40 to 13: step1 24 45 30 32 28 min[H] 90 40 44 29 7 19 6 12 4 22 17 n[H] 清华大学 宋斌恒 33 Decrease 40 to 13: step2 24 45 30 32 28 min[H] 90 13 44 29 7 19 6 12 4 22 17 n[H] 如果 13小于 min[H],则改变 min[H]指针 清华大学 宋斌恒 34 46减少为15 清华大学 宋斌恒 35 把b）的35降为5 清华大学 宋斌恒 36 合并：H1和H2 24 45 30 32 28 min[H1} 90 5 44 29 7 19 6 12 4 22 17 min[H2]
合并:H1和H2合并其root 合并:H1和H2合并其root list,即双向链表的合并 list,即双向链表的合并 ③、m@mx ④③ 清华大学宋域恒 请华大学宋恒 合并:H和H2合并其root Extract the min:对root进行合 list,即双向链表的合并 并:一次顺序扫描 清华大学末斌恒 请华大学宋恒 Extract the min:对root进行合 Extract the min:对root进行合 并:一次顺序扫描 并:一次顺序扫描 123 0123 ③-0●-① -●一① ④④ 清华大学末破恒 请华大学宋
7 清华大学 宋斌恒 37 合并：H1和H2:合并其root list，即双向链表的合并 24 45 30 32 28 min[H1} 90 5 44 29 7 19 6 12 4 22 17 min[H2] 清华大学 宋斌恒 38 合并：H1和H2:合并其root list，即双向链表的合并 24 45 30 32 28 min[H1} 90 5 44 29 7 19 6 12 4 22 17 min[H2] 清华大学 宋斌恒 39 合并：H1和H2:合并其root list，即双向链表的合并 24 45 30 32 28 min[H] 90 5 44 29 7 19 6 12 4 22 17 清华大学 宋斌恒 40 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 min[H] 90 5 44 29 7 19 6 12 4 22 17 清华大学 宋斌恒 41 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 5 90 44 29 7 19 6 12 22 17 0 1 2 3 清华大学 宋斌恒 42 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 5 90 44 29 7 19 6 12 22 17 0 1 2 3
Extract the min:对root进行合 Extract the min:对root进行合 并:一次顺序扫描 并:一次顺序扫描 □23 0123 -●一① 清华大学宋域恒 请华大学宋恒 Extract the min:对roo进行合 Extract the min:对root进行合 并:一次顺序扫描 并:一次顺序扫描 o12 23 —@ ④④ 清华大学末斌恒 请华大学宋恒 Extract the min:对root进行合 Extract the min:对root进行合 并:一次顺序扫描 并:一次顺序扫描 巴中口 01234 ④④ 清华大学末域恒 ④④ 请华大学宋
8 清华大学 宋斌恒 43 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 5 90 44 29 7 19 6 12 22 17 0 1 2 3 清华大学 宋斌恒 44 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 5 90 44 29 7 19 6 12 22 17 0 1 2 3 清华大学 宋斌恒 45 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 5 90 44 29 7 19 6 12 22 17 0 1 2 3 清华大学 宋斌恒 46 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 90 28 5 44 29 7 19 6 12 22 17 0 1 2 3 清华大学 宋斌恒 47 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 90 28 5 44 7 29 19 6 12 22 17 0 1 2 3 清华大学 宋斌恒 48 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 5 90 44 29 7 19 6 12 22 17 0 1 2 3 4
FIB-HEAP-EKTRACT-L《品 5 far each wade w in the oot lr af w 2ifa≠ML Md r to the root list of冒 第一步 tf texel >hexr if i= righTer. manla right[al a[←叫[5-1 Ir ta the tort lir sf n 12 return if ulm a IIL cc her) c lerandI 其它操作 意义 删除 heretical A good example for applying potential 可以由其它操作合并完成 function 清华大学末斌恒 请华大学宋恒 总结 · Fibonacci堆的定义及其操作 ·针对不同操作,设计各种方法以达到某 种目的。 清华大学末破恒
9 清华大学 宋斌恒 49 第一步 清华大学 宋斌恒 50 清华大学 宋斌恒 51 其它操作 • 删除 • Insert • 可以由其它操作合并完成 清华大学 宋斌恒 52 意义 • Theoretical • A good example for applying potential function 清华大学 宋斌恒 53 总结 • Fibonacci堆的定义及其操作 • 针对不同操作，设计各种方法以达到某 种目的