Data Structures and Algorithms with Object-Oriented Design Patterns in C++

## Binomial Queues

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 non-negative 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

The merging of and is done in the same way:

 +

Therefore, the result is .