6 4 9 5 8 7 3 1 9 5 6 5 9 2 8 6 7 4 Collection of min trees.
Way in which operations are performed constrains the tree structure.
Node Structure
Degree
Number of children.
Child
Pointer to one of the node’s children.
Null iff node has no child.
Sibling
Used for circular linked list of siblings.
Data
Space requirements are similar to those of a leftist tree. Now we have a degree field instead of an s-value field. As we shall see, degree and s-values are both O(log n).
Binomial Heap Representation
Circular linked list of min trees. 6 4 9 5 8 7 3 1 9 5 6 5 9 2 8 6 7 4 A Degree fields not shown.
Insert 10
10 Update min-element pointer if necessary. 6 4 9 5 8 7 3 1 9 5 6 5 9 2 8 6 7 4 A Add a new single-node min tree to the collection.
New tree is added next to tree with min element. This takes O(1) time.
Meld
9 5 7 A 4 8 7 3 1 B Set min-element pointer. Combine the 2 top-level circular lists.
O(1) time.
Meld
9 5 7 4 8 7 3 1 C
Remove Min
Empty binomial heap => fail.
Nonempty Binomial Heap
10 6 4 9 5 8 7 3 1 9 5 6 5 9 2 8 6 7 4 A Remove a min tree.
Reinsert subtrees of removed min tree.
Update binomial heap pointer.
Remove Min Tree
a b c d e A No next node => empty after remove.
Otherwise, copy next-node data and remove next node. d Same as remove a node from a circular list.
Reinsert Subtrees
9 5 7 A 4 8 7 3 1 B subtrees Combine the 2 top-level circular lists.
Same as in meld operation.
Update Binomial Heap Pointer
Must examine roots of all min trees to determine the min value.
Complexity Of Remove Min
Remove a min tree.
O(1).
Reinsert subtrees.
O(1).
Update binomial heap pointer.
O(s), where s is the number of min trees in final top-level circular list.
s = O(n).
Overall complexity of remove min is O(n).
Since our remove min operation has to walk through original top-level circular list, we may as well do the removal of the min tree during this walk (instead of using the copy from forward node trick) .
Enhanced Remove Min
During reinsert of subtrees, pairwise combine min trees whose roots have equal degree.
Pairwise Combine
10 6 4 9 5 8 7 3 1 9 5 6 5 9 2 8 6 7 4 Examine the s = 7 trees in some order. Determined by the 2 top-level circular lists.
One of the top-level circular lists is the original top-level list (minus the removed min tree); the other is the list of the removed min tree’s subtrees.
Pairwise Combine
10 6 4 9 5 8 7 3 1 9 5 6 5 9 2 8 6 7 4 Use a table to keep track of trees by degree. 1 2 3 4 tree table 0
Comments