Remember the choose function we discussed in Chapter 4, Detour - Functional Programming? There, I pointed out that it is also called the binomial coefficient. Let's see how it is related to a binomial tree. Suppose we have a binomial tree of height h and we want to find out the number of nodes at level l. Let's assume that for a tree of height h, the number of nodes is f(t,r), where t=h-1 and r = l-1. The reason for taking a variable that is one less than the height and level will become clearer a little later. Basically, t is the height of the tree that starts from 0 instead of 1, and r is the level that starts from zero. Now this tree is obviously a tree of only one element or it is made up of two trees of height h-1 = t:

Figure 7. The rationale for naming it a binomial tree

We will call these two subtrees this: red subtree and green subtree. This is because they are colored this way in the preceding figure. The levels are highlighted using dashed lines. It is clear from the picture that the nodes at the level r in the complete tree is either at level r in the red tree or at level r-1 in the green tree. Both the red and green trees are trees of height h-1. This means the following: f(t,r) = f(t-1,r) + f(t-1,r-1). This equation is the same as what we have for the choose function we have already discussed. The only thing we have to check is the boundary conditions. The top level (that is t=0) always has only one node, so f(t,0) = 1. We also know that the number of levels in the tree has to be less than or equal to the height of the tree, so we have f(t,r) = 0 if t <r. So, f(t,t) = f(t-1,t) + f(t-1,t-1) = 0 + f(t-1,t-1) = f(t-1,t-1) for any t. In the same way, f(t-1,t-1) = f(t-2,t-2) = f(t-3,t-3) = … = f(0,0) = 1 (because f(t,0) = 1). Therefore, all the conditions of the choose function are satisfied; hence we can see f(t,r) = choose(t,r) = choose(h-1, l-1). Since the choose function is also called the binomial coefficient, this gives the binomial tree its name.

What is the number of nodes n in a binomial tree of height h? When h=1, we only have one node. A tree of height 2 is made up of two trees of height 1, a tree of height 3 is made up of two trees of height 2, and so on. So, for the increment of 1 in height, the number of nodes must be twice as much as the original number. That is, when h=1, n=1; h=2, n=2; h=3, n=4,... In general, this should be the case: n = 2 ^h-1= 2 ^t. Here t is the height starting from zero.

Notice also that we can say that the number of nodes n in a tree is the sum of the number of nodes in each level, which is choose(t, r), where r is the level starting from 0 to t. The two formulas must be equal, so the sum choose(t, 0) + choose(t, 1) + choose(t, 2) + … + choose(t, t) equals 2 ^t. This is a proof of this relationship. There are other proofs as well, but this is a valid proof too.

Of course, with only this structure, we have no way of making sure of having some easy way of figuring out the minimum element. So, we also enforce the heap property on a binomial tree:

Figure 8. Preserving heap property while merging.

This is the property: the value of any node is smaller than the value of each of its children. When merging two trees to make one, the only thing we need to do to preserve the heap property is to use the heap with the lesser value at its top node as the top subtree and the one with the higher value at its top node as the subordinate subtree. This is shown in the preceding figure. The red tree happens to have a higher value in the root node than that of the green tree. Hence, the red tree must be the subordinate tree. The heap property ensures that the root of any binomial tree holds the minimum element.

So how do we make a queue out of this? Firstly, note that any tree will have nodes with at least the power of 2. But, in a queue, we want an arbitrary number of elements. So we store these elements in more than one tree. Any number can be expressed as the sum of the power of 2 because any number can be expressed in binary form. Suppose we need to store 20 nodes. The number 20 in binary is 10100. So we need two binomial trees: one with height 5 and 16 nodes and one with height 3 and four nodes. A queue is built using a collection of binomial trees to store the nodes. Hence it is called a binomial forest.

Before we discuss how to insert new elements and remove the minimum element, we need to understand how to merge two binomial forests. We have already seen that the numbers of elements are represented according to binary form. Just write the number in binary form, and if 1 exists, it means there is a tree of height that is equal to one plus its position from right to left. When we merge two forests, the number of elements of the merged forest is the sum of the number of elements in the forests that need to be merged. This means the result will have trees of sizes where the binary representation of the sum will have the number 1. We can find this binary representation by performing a binary addition of the binary representations of the node's source number. For example, let's merge two forests: one with 12 elements and one with 10 elements. Their binary representations will be 1100 and 1010, respectively. If we do a binary addition, we have 1100 + 1010 = 10110. This means the original trees had trees of heights 3, 5 and 4, 5 and the result must have trees of heights 3, 4, and 6. The merge happens the same way we do a binary addition. The trees are stored in sequence, and we have empty places that represent zeros in the binary representation. While merging, each tree represents a bit and it has the number of nodes that the bit represents. We take the corresponding bit from each forest and also consider a carry. All these trees must either be empty or have exactly the same number of nodes. Then, we merge them to create the resulting bits.

To do any binary addition, we have input of three bits for each bit: one from each of the input and a carry. We need to compute both the output bit and the next carry. Similarly, while merging two trees, we need to compute the output tree and the carry tree from the given input trees (two) and a carry tree. Once the merging is done, inserting and removing min is simple.

The insert simply merges a forest with a single tree using a single node. Removing the minimum element is a little more complicated operation. The first step is to find out the minimum. We know every tree has the minimum element at its root. So we need to walk through all the trees while comparing the root elements to find the minimum element and the tree that has it. Removing it is simply taking the root off, leaving a list of subtrees that make a forest of consecutive heights of trees. Therefore, we can merge the subtrees in the main forest to complete the removal process.

Let's see the implementation. First, we create a skeleton class. A binomial tree has a root, which contains a value and a list of subtrees. The list of subtrees is like a dense forest. The list of trees in the forest is stored in a linked list. We use DoublyLinkedList because we need to remove the last element:

public class BinomialForest<E> implements PriorityQueue<E>{

    protected Comparator<E> comparator;
    protected static class BinomialTree<E>{
        E value;
        LinkedList<BinomialTree<E>> subTrees = new LinkedList<>();
        public BinomialTree(E value){
            this.value = value;
        }
    }

    public BinomialForest(Comparator<E> comparator){
        this.comparator = comparator;
    }



    DoublyLinkedList<BinomialTree<E>> allTrees = new DoublyLinkedList<>();
    …
}

As discussed earlier, we will start with the merge operation now. First we need to merge two trees, which we will use to merge two forests. Merging two trees is a simple constant time operation. Merging with a null tree does not change the tree. The two trees being merged should be of the same size. We need to simply compare the root elements. The tree with the smaller value in its root will get the other as a child:

    protected BinomialTree<E> merge(BinomialTree<E> left, 
      BinomialTree<E> right){

        if(left==null){
            return right;
        }else if(right==null){
            return left;
        }
        if(left.subTrees.getLength() != right.subTrees.getLength()){
            throw new IllegalArgumentException(
                  "Trying to merge two unequal trees of sizes " +
                    left.subTrees.getLength() + " and " + right.subTrees.getLength());
        }
        if(comparator.compare(left.value, right.value)<0){
            left.subTrees.appendLast(right);
            return left;
        }else{
            right.subTrees.appendLast(left);
            return right;
        }
    }

Since we want to check the minimum element in constant time, just like in a heap, we will store the minimum element in a state variable. We will also store its position in the allTrees list:

    BinomialTree<E> minTree = null;
    int minTreeIndex = -1;

We will define a method to find out and update the variables. Since the smallest element in any tree is the root, we only have to go through the root to find the minimum element:

    protected void updateMinTree(){
        if(allTrees.getLength()==0){
            minTree = null;
            minTreeIndex = -1;
        }
        E min = null;
        int index = 0;
        for(BinomialTree<E> tree:allTrees){
            if(tree==null){
                index++;
                continue;
            }
            if(min == null || comparator.compare(min, tree.value)>0){
                min = tree.value;
                minTree = tree;
                minTreeIndex = index;
            }
            index++;
        }
    }

To implement the merging of two forests, we need to first implement how to compute the output and carry the tree out of the two input trees and a carry tree. These methods are fairly simple. We need to understand that both the input and the carry must be of the same size if they are not null. The height of the output must be the same as the height of the output, and the height of the carry must be one more than the height of the input:

    protected BinomialTree<E> computeOutputWithoutCarry(BinomialTree<E> lhs, BinomialTree<E> rhs, BinomialTree<E> carry){
        if(carry==null){
            if(lhs==null){
                return rhs;
            }else if(rhs==null){
                return lhs;
            }else{
                return null;
            }
        }else{
            if(lhs==null && rhs==null){
                return carry;
            }else if(lhs == null){
                return null;
            }else if(rhs == null){
                return null;
            }else{
                return carry;
            }
        }
    }
    protected BinomialTree<E>  computeCarry(
      BinomialTree<E> lhs, BinomialTree<E> rhs, BinomialTree<E> carry){
        if(carry==null){
            if(lhs!=null && rhs!=null){
                return merge(lhs, rhs);
            }else{
                return null;
            }
        }else{
            if(lhs==null && rhs==null){
                return null;
            }else if(lhs == null){
                return merge(carry, rhs);
            }else if(rhs == null){
                return merge(carry, lhs);
            }else{
                return merge(lhs, rhs);
            }
        }
    }

We also need to enhance the ListIterator class in our imperative LinkedList implementation so that we can modify the value of any node while iterating through it. We use the following implementation to do this:

    public class ListIterator implements Iterator<E> {
        protected Node<E> nextNode = first;
        protected Node<E> currentNode = null;
        protected Node<E> prevNode = null;

        @Override
        public boolean hasNext() {
            return nextNode != null;
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new IllegalStateException();
            }
            prevNode = currentNode;
            currentNode = nextNode;
            nextNode = nextNode.next;
            return currentNode.value;
        }

        @Override
        public void remove() {
            if(currentNode==null || currentNode == prevNode){
                throw new IllegalStateException();
            }
            if(currentNode==first){
                first = nextNode;
            }else{
                prevNode.next = nextNode;
            }
            currentNode=prevNode;

        }

        public void setValue(E value){
            currentNode.value = value;
        }

    }

With these methods available, we can implement the merging of two forests or two lists of trees:

    protected void merge(LinkedList<BinomialTree<E>> rhs){
        LinkedList<BinomialTree<E>>.ListIterator lhsIter
          = (LinkedList<BinomialTree<E>>.ListIterator)allTrees.iterator();
        Iterator<BinomialTree<E>> rhsIter = rhs.iterator();
        BinomialTree<E> carry = null;
        while(lhsIter.hasNext() || rhsIter.hasNext()){
            boolean lhsHasValue = lhsIter.hasNext();
            BinomialTree<E> lhsTree = lhsHasValue? lhsIter.next():null;
            BinomialTree<E> rhsTree = rhsIter.hasNext()? rhsIter.next():null;
            BinomialTree<E> entry = computeOutputWithoutCarry(lhsTree, rhsTree, carry);
            carry = computeCarry(lhsTree, rhsTree, carry);
            if(lhsHasValue) {
                lhsIter.setValue(entry);
            }else{
                this.allTrees.appendLast(entry);
            }
        }
        if(carry!=null){
            this.allTrees.appendLast(carry);
        }
        updateMinTree();
    }

The Insert method is very simple to implement with the merge available. Just merge a list containing one tree with the value 1:

    public void insert(E value){
        BinomialTree<E> newTree = new BinomialTree<E>(value);
        DoublyLinkedList<BinomialTree<E>> newList 
               = new DoublyLinkedList<>();
        newList.appendLast(newTree);
        merge(newList);
    }

Removal of the minimum element is a little more complex. It involves removing the tree with the minimum value and then considering its root as the minimum element. Once this is done, the subtrees need to be merged with the original forest. If the last tree is being removed, we must actually remove it from the list. This is the same as not writing a leading zero in binary representation. Otherwise, we only set the value to null so that we know it is a zero bit:

    public E removeMin(){
        if(allTrees.getLength()==0){
            return null;
        }
        E min = minTree.value;
        if(minTreeIndex==allTrees.getLength()-1){
            allTrees.removeLast();
        }else {
            allTrees.setValueAtIndex(minTreeIndex, null);
        }
        merge(minTree.subTrees);
        return min;
    }

Finally, we can implement the methods required to use it as a priority queue:

    @Override
    public E dequeueMinimum() {
        return removeMin();
    }

    @Override
    public void enqueue(E value) {
        insert(value);
    }

    @Override
    public Iterator<E> iterator() {
        return null;
    }

This completes our implementation of a binomial queue.

We already know that the number of nodes in a binomial tree of height h is 2h-1. The question is, if we want to store n elements, what should be the maximum height of the trees in the forest? We have seen that the trees we need are as per the binary expression of the integer n. The most significant bit of the binary representation of n is the floor of (lg n), that is the greatest integer less than or equal to lg n. We will write this as lg n. The height of the tree representing this bit is 1 + lg n. The length of the list holding the trees in the forest is also 1 + lg n= θ(lg n). Both in the case of an insertion and removal of a new element, a merge operation is involved. The merge operation is constant time for each pair of input trees and one carry. So, the number of operations for a merge operation of two forests is this: constant times the number of trees in the largest forest = θ(lg n), where n is the number of trees in the largest forest.

At the time of insertion, we just merge a new forest of only one tree and one element. So this operation is θ(lg n), where n is the number of elements in the original forest.

The removal process involves two steps. The first is to remove the minimum element. This involves a constant time operation, which is used to remove the tree with the minimum element, and a merge operation, which is θ(lg n), as seen already. The second step/operation is to update the tree with the minimum element. This involves scanning the roots of all the trees; therefore, it is θ(lg n), just like the merge operation. So, as a whole, the removal process is also θ(lg n).

Checking the minimum element is of course constant time, as we have it referenced already.