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