CMSC 341 Binomial Queues and Fibonacci Heaps Basic Heap Operations Op insert Binary Heap O lgN Leftist Heap O lgN deleteMin O lgN O lgN decrease O lgN O lgN Key merge O N O lgN findMin O 1 O 1 Binomial Queue Fibonacci Heap Amortized Time Binomial Queues and Fibonacci Heaps have better performance in an amortized sense Cost per operation vs cost for sequence of operations RB trees are O lgN per operation Splay trees are O M lgN for M operations Individual ops can be more less expensive that O lgN If one is more expensive another is guaranteed to be less On average cost per op is O lgN Basic Heap Operations Op insert Binary Heap O lgN Leftist Heap O lgN deleteMin O lgN O lgN Binomial Queue O 1 amortized O lgN decrease O lgN O lgN O lgN Key merge O N O lgN O lgN findMin O 1 O 1 O 1 Fibonacci Heap Basic Heap Operations Op insert Binary Heap O lgN Leftist Heap O lgN deleteMin O lgN O lgN Binomial Queue O 1 amortized O lgN decrease O lgN O lgN O lgN Key merge O N O lgN O lgN findMin O 1 O 1 O 1 Fibonacci Heap O 1 amortized O lgN amortized O 1 amortized O 1 amortized O 1 amortized Binomial Tree Has heap order property Bk binomial tree of height k B0 tree with one node Bk formed by adding a Bk 1 as child of root of another Bk 1 Bk has exactly 2K nodes why Binomial Trees B0 B3 B1 B2 Binomial Queue A collection list of Binomial Trees A forest No more than one Bk in queue for each k Queue with N nodes contains no more than lgN trees why findMin Scan trees and return smallest root O lgN because there are O lgN trees Keep track of tree with smallest root Update due to other operations e g insert deleteMin O 1 merge Merge Q1 and Q2 creating Q3 Q3 can contain only one Bk for each k If only one of Q1 and Q2 contain a Bk add it to Q3 What if Q1 and Q2 both contain a Bk Merge them and add a Bk 1 to Q3 Now what if Q1 Q2 or both contain a Bk 1 Merge until there are zero or one of them merge Think of Q1 and Q2 as binary integers Bit k 1 iff queue contains a Bk Compute Q3 Q1 Q2 To compute value of bit k for Q3 Add bit k from Q1 and Q2 and carry from position k 1 Adding bits corresponds to merging trees May generate carry bit tree to position k 1 merge Complexity is O lgN There are O lgN trees in Q1 and Q2 Merging trees takes O 1 merge example Q1 16 12 18 21 24 65 Q2 13 14 23 26 51 24 65 Q1 16 12 18 Q2 13 14 21 23 26 Q3 24 65 24 51 65 Q1 16 12 18 Q2 13 14 13 21 23 26 Q3 24 65 24 51 65 Q1 16 12 18 Q2 13 14 21 23 26 Q3 13 24 65 24 51 14 65 16 26 18 Q1 16 12 18 Q2 13 14 14 16 26 18 21 23 26 13 24 65 24 51 65 Q1 16 12 24 18 Q2 13 14 21 23 24 26 13 14 26 51 12 16 18 65 21 24 65 23 65 24 51 65 insert Insert value X into queue Q Create binomial queue Q with B0 containing X Merge Q with Q Worst case O lgN because Q can contain lgN trees Suppose Bi is smallest tree not in Q then time is O i insert Suppose probability that Q contains Bk for any k is 1 2 Probability that Bi is smallest tree not in Q is 1 2i why The expected value of i is then i 1 2i 2 On average insertion will require a single merge and is therefore O 1 amortized deleteMin Find tree with minimum root and remove root Treat sub trees of root as a new binomial queue Merge this new queue with the original one O lgN Fibonacci Heap All heap operations take O 1 amortized time Except deleteMin which takes O lgN amortized time Implemented using Binomial Queue Two new ideas Lazy merging New implementation of decreaseKey Lazy Merging To merge Q1 and Q2 just concatenate lists of Binomial Trees This takes O 1 time Result may contain multiple Bk for any given k we ll deal with this in a minute Insertion is now O 1 why deleteMin Scan list of trees for one with smallest root No longer guaranteed to be O lgN because of duplicate Bk from lazy merging Remove root and lazily merge sub trees with binomial queue Reinstate binomial queue by merging trees to ensure at most one Bk for any k Reinstating a Binomial Queue R rank of tree number of children of root LR set of all trees of rank R in queue T number of trees in queue Code below is O T lgN why for R 0 R lgN R while LR 2 remove two trees from LR merge them into a new tree add the new tree to LR 1 deleteMin Example 5 3 6 9 10 15 21 4 7 11 8 18 20 deleteMin Example 5 3 6 Remove this node 9 10 15 21 4 7 11 8 18 20 deleteMin Example More than one B0 tree merge 5 6 9 10 15 21 4 7 11 8 18 20 deleteMin Example More than one B1 tree merge 5 6 9 10 15 21 4 7 11 8 18 20 deleteMin Example 5 6 9 10 15 21 4 7 11 Still more than one B1 tree merge 8 18 20 deleteMin Example More than one B2 tree merge 6 9 15 21 4 7 11 5 8 10 18 20 deleteMin Example 6 9 7 15 21 4 11 5 10 8 18 20 Complexity of deleteMin Theorem The amortized running time of deleteMin is O lgN Proof It s a bit tricky But it s in the text for those with burning curiosity decreaseKey Standard approach is to change value decrease it and percolate up Not O 1 which is goal unless height of tree is O 1 Instead decrease value and then cut link between node and parent yielding two trees Cut Example 3 15 9 21 Decrease key 15 to 1 3 3 1 9 Cut 21 1 9 21 Cascading Cuts When cutting do the following Mark a non root node the first time that it loses a child due to a cut If a marked node loses another child then cut it from its parent This node becomes the root of a separate tree that is no longer marked This is called a cascading cut because several could occur due to a single decreaseKey Cascading Cuts Example 3 5 10 33 35 13 Parts of tree not shown …
View Full Document
Unlocking...