算法分析与设计2005春.课件.第13讲.pdf

Over view on Heaps
Operation Binary heap Binomial i
heap heap
第13讲:Binomial & i Creation Θ(1) Θ(1) Θ(1)
Insert Θ(lg n) Ο(lg n) Θ(1)
Heaps Minimum Θ(1) Ο(lg n) Θ(1)
清华大学 Extract-min Θ(lg n) Θ(lg n) Ο(lg n)
Union n lg n
宋斌恒Θ( ) Ο( ) Θ(1)
Decrease-key Θ(lg n) Θ(lg n) Θ(1)
Delete Θ(lg n) Θ(lg n) Ο(lg n)
清华大学宋斌恒 2
Over parison 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 • i 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
清华大学宋斌恒 3 清华大学宋斌恒 4
Common issues Binomial trees
• It is inefficient to support the operation of • Binomial trees Bk are defined reclusively as
search for all kinds of the heaps, so it needs – B0 consists of a single node
to visit the elements by its handle or the – The Bk consists of two Bk-1 that are linked
pointer together: the root of one Bk-1 is the left most
child of another one Bk-1.
清华大学宋斌恒 5 清华大学宋斌恒 6
1
Depth
0
1
2
3
B0 B1 B2 B3
清华大学宋斌恒 7 清华大学宋斌恒 8
Properties Proof of the properties
• For binomial tree Bk: • All by induction, because it is defined
1. There are 2k nodes. recursively. Here we omit the proof.
2. The height of the tree