If binomial trees only come in sizes that are powers of two, how do we implement a container which holds an arbitrary number number of items n using binomial trees? The answer is related to the binary representation of the number n. Every nonnegative integer n can be expressed in binary form as
where is the binary digit or bit in the representation of n. For example, n=27 is expressed as the binary number because 27=16+8+2+1.
To make a container which holds exactly n items we use a collection of binomial trees. A collection of trees is called a forest . The forest contains binomial tree if the bit in the binary representation of n is a one. I.e., the forest which contains exactly n items is given by
where is determined from Equation . For example, the forest which contains 27 items is
The analogy between and the binary representation of n carries over to the merge operation. Suppose we have two forests, say and . Since contains n items and contains m items, the combination of the two contains n+m items. Therefore, the resulting forest is .
For example, consider n=27 and m=10. In this case, we need to merge with . Recall that two binomial trees of order k can be combined to obtain a binomial tree of order k+1. E.g., . But this is just like adding binary digits! In binary notation, the sum 27+10 is calculated like this:
1  1  0  1  1  
+  1  0  1  0  
 1  0  0  1  0  1 
+  
