Equivalently, a Bk tree is a general tree whose root has k children, the rth of which is a Br-1 tree. So we have, for example:
* * * *
| / \ / | \
* * * * * *
| | / \
* * * *
|
*
showing B0 through B3. The first definition above tells
us that if Nk is the number of nodes in a binomial tree Bk, then Nk+1 = 2Nk, and since N0 = 1,
then Nk = 2k, k = 0,1,2,.... .If we want to find the height Hk of a Bk tree, we see that it's 1 + Hk-1, and since H0 = 0, we have Hk = k, k = 0,1,2, . .
Finally, it's not too difficult to show that the number of nodes at level r in a Bk tree (r = 0, 1, 2, ....., k) is: the binomial coefficient k!/r!(k-r)!. This property of the trees gives them their name: binomial trees.
A binomial queue is a forest of binomial trees, where at most one tree of each index may be present. The picture at the top of this note is a binomial queue containing 1 + 2 + 4 + 8 = 15 nodes. You can remove one or more of the trees to get different binomial queues, and of course you can include binomial trees of higher order. How would you achieve a binomial queue with 5 nodes? With 11 nodes? With 23 nodes? Look carefully at which trees are present in each forest, and how the total number of nodes is achieved.
We say that two binomial trees of the same order can be merged by attaching one as a subtree (the rightmost) of the other. Note that this produces a tree whose index is one greater than the trees we started with.
If we have labels (keys) on the nodes of a binomial tree, and we impose an ordering property where the parent key is larger than the keys of any of its children, we can construct a heap with a binomial queue. We'll build a heap by processing the keys A L G O R I T H M.
A --> L (we merged two trees of index 0 into a tree of
| index 1 - and also maintained the heap property
A by comparing the root keys and using the larger to
root the resulting tree)
--> G L (we can keep a pointer to the root with the largest
| key and update as necessary when a new key is
A inserted; now it points to L)
--> O L (we merged the O tree and the G tree, but we must
| | now merge the two trees of order 1, since we're
G A only permitted at most one tree of any index. we
attach the root of the tree with the smaller root
key as a new child of the root with the larger
key, and point the max_key pointer at O.)
--> O --> R O (no merging, but pointer to max_key updated)
/ \ / \
G L G L
| |
A A
--> R O --> T R O --> T R O --> T O
| / \ | / \ | | / \ / \ / \
I G L I G L H I G L H R G L
| | | | |
A A A I A
--> T --> M T
/ | \ / | \
H R O H R O
| / \ | / \
I G L I G L
| |
A A
and we finish with a (key ordered) binomial queue - a binomial heap -
containing a binomial tree of order 0 and a tree of order 3. Notice that when
the key H was inserted into the binomial heap several merges took place. T and
H were merged into a binomial tree of index 1, but since there was a already a
tree of index 1 (with root R) another merge took place producing a tree of
index 2 - but there was another tree already present of index 2 (with root O)
so these two trees were merged into a binomial tree of index 3. What does this
merging (and chains of merges) remind you of?? How many binomial trees are required to store a binomial heap of n nodes? In a binomial heap of n nodes, how many merges (at worst) will occur when another key is added to the heap? How many merges (at most) will take place when we build a binomial heap of n nodes beginning with an empty heap? What is the average cost (in merges) of inserting a new key into a binomial heap containing n items?
In order to use the binomial queue as a heap, we must be able to delete (remove) the largest key, and restore the heap. We have maintained a pointer to the node with the largest key, updating as necessary when new keys are inserted (or, we can simply scan for the largest key over the roots of the trees: there are at most lgn of them). That node is of course the root of one of the binomial trees in the forest, and deleting it leaves us with - a forest of its children. This forest needs to be merged with the forest comprised of the other binomial trees in the heap. Consider deleting T from the heap previously constructed. We have to merge two forests, one consisting of the (single) tree M, the other the forest whose tree roots are H, R, and O. So the index-zero trees M and H are merged into an index-one tree (with M as the root), but that must be merged with the index-one tree whose root is R, producing an index-two tree rooted at R - but this must be merged with the index-two tree rooted at O, so the final result is the one-tree forest:
R
/ | \
I M O
| / \
H G L
|
A
and the max_key pointer points to R. At worst, then, how many merges are caused
by the deletion of the largest key from a binomial heap with n nodes??How do we represent binomial queues/heaps? With the natural correspondence of course: the binary tree representative (!) We'll need to modify the binary tree implementation a little so that it can support the operations necessary to insert/delete in a binomial heap. The merging of two binomial trees (of the same index) requires linking one tree as a new child of the root of the other tree. This is a "unit-cost" operation - but not when we process the binary tree representing the forest of binomial trees. We have to follow a linked list of right pointers to find the right-most, and link in the root of the other tree. In order to maintain this as "unit-cost", we'll need to add a pointer field to every node which indentifies it's "last" (right-most) child. Furthermore, since we can merge only binomial trees of the same index, we'll need an integer field on each node which gives the index of the binomial tree rooted at that node. There may be other modifications necessary to facilitate processing the binary tree representative of the binomial heap, but these changes are essential.
class BtrNode {
protected char key; // single-character node labels
protected BtrNode L, R, last;
int index;
// constructors, setters, and getters
}
class BT {
protected BtrNode root;
public BT binomialMerge(BT s, BT t){
/* merges the binary representations of the two binomial
trees; returns the BT of the merged result */
// other methods
}
where root is a pointer to the root of the binary tree representing the
binomial heap. Can you write the method binomialMerge that merges the
binary representatives of two binomial trees into the binary representative of
the merged binomial tree? Binomial heaps are important because of the efficient way in which two heaps can be merged. If you consider merging two binary heaps, each stored in an array, the only way is to "concatenate" the two arrays, and build a composite heap. If the two heaps contain m and n items, then the worst-case cost of the merge is O(m+n). Compare this with the worst-case cost of merging two binomial heaps.