1 第13讲：Binomial & Fibonacci Heaps 清华大学 宋斌恒 清华大学宋斌恒2 HeapsonviewOver Ο(lg n)Θ(lg n)Θ(lg n)Delete Θ(1)Θ(lg n)Θ(lg n) Decrease-key Θ(1)Ο(lg n)Θ( n)Union Ο(lg n)Θ(lg n)Θ(lg n)Extract-min Θ(1)Ο(lg n)Θ(1)Minimum Θ(1)Ο(lg n)Θ(lg n)Insert Θ(1)Θ(1)Θ(1)Creation Fibonacci heap Binomial heap Binary heapOperation 清华大学宋斌恒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 B k are defined reclusively as – B 0 consists of a single node – The B k consists of two B k-1 that are linked together: the root of one B k-1 is the left most child of another one B k-1 . 2 清华大学宋斌恒7 B 0 B 1 B 2 B 3 0 1 2 3 Depth 清华大学宋斌恒8 清华大学宋斌恒9 Properties ? For binomial tree B k : 1. There are 2 k 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 B i . 清华大学宋斌恒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 binomial- heap 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 B k in H. 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 合并步骤 ?第一步：融合，按照树的大小从小到大 排列两个堆的所有二项式树 ?第二步：从小到大联结相同的二项式 树：如果当前大小相同的树连续只有一 个跳过，只有两个联结，只有三个则联 结后两个，然后继续. 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 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 完全表示方式 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] 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 905 44 29 7 19 6 12 22 17 3210 清华大学宋斌恒42 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 905 44 29 7 19 6 12 22 17 3210 8 清华大学宋斌恒43 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 905 44 29 7 19 6 12 22 17 3210 清华大学宋斌恒44 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 905 44 29 7 19 6 12 22 17 3210 清华大学宋斌恒45 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 905 44 29 7 19 6 12 22 17 3210 清华大学宋斌恒46 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 2890 5 44 29 7 19 6 12 22 17 3210 清华大学宋斌恒47 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 2890 5 44 29 7 19 6 12 22 17 3210 清华大学宋斌恒48 Extract the min: 对root进行合 并：一次顺序扫描 24 45 30 32 28 905 44 29 7 19 6 12 22 17 34210 9 清华大学宋斌恒49 第一步 清华大学宋斌恒50 清华大学宋斌恒51 其它操作 ?删除 ? Insert ?可以由其它操作合并完成 清华大学宋斌恒52 意义 ? Theoretical ? A good example for applying potential function 清华大学宋斌恒53 总结 ? Fibonacci堆的定义及其操作 ?针对不同操作，设计各种方法以达到某 种目的。