Data Structure - Binomial Queue (Java)

package chimomo.learning.java.datastructure;

/**
 * Implements a binomial queue.
 * Note that all "matching" is based on the compareTo method.
 *
 * @author Created by Chimomo
 */
public final class BinomialQueue<T extends Comparable<? super T>> {
    private static final int DEFAULT_TREES = 1;

    // # items in priority queue.
    private int size;

    // An array of tree roots.
    private BinomialNode<T>[] trees;

    /**
     * Construct the binomial queue.
     */
    public BinomialQueue() {
        trees = new BinomialNode[DEFAULT_TREES];
        makeEmpty();
    }

    /**
     * Construct with a single item.
     */
    public BinomialQueue(T item) {
        size = 1;
        trees = new BinomialNode[1];
        trees[0] = new BinomialNode<>(item, null, null);
    }

    /**
     * Test program.
     *
     * @param args The arguments.
     */
    public static void main(String[] args) throws Exception {
        // Construct binomial queue.
        int numItems = 10000;
        BinomialQueue<Integer> bq1 = new BinomialQueue<>();
        BinomialQueue<Integer> bq2 = new BinomialQueue<>();
        int i;
        System.out.println("Starting check.");

        // Insert.
        for (i = 37; i != 0; i = (i + 37) % numItems) {
            if (i % 2 == 0) {
                bq2.insert(i);
            } else {
                bq1.insert(i);
            }
        }

        // Merge.
        bq1.merge(bq2);

        // Delete min.
        for (i = 1; i < numItems; i++) {
            if (bq1.deleteMin() != i) {
                System.out.println("Oops! " + i);
            }
        }
        System.out.println("Check done.");
    }

    /**
     * Expand trees.
     *
     * @param newNumTrees The new number of trees.
     */
    private void expandTrees(int newNumTrees) {
        BinomialNode<T>[] old = trees;
        int oldNumTrees = trees.length;

        trees = new BinomialNode[newNumTrees];
        for (int i = 0; i < Math.min(oldNumTrees, newNumTrees); i++) {
            trees[i] = old[i];
        }
        for (int i = oldNumTrees; i < newNumTrees; i++) {
            trees[i] = null;
        }
    }

    /**
     * Merge binomial queue into the priority queue.
     * Binomial queue becomes empty.
     * Binomial queue must be different from this.
     *
     * @param binomialQueue The other binomial queue.
     */
    public void merge(BinomialQueue<T> binomialQueue) {
        // Avoid aliasing problems.
        if (this == binomialQueue) {
            return;
        }

        size += binomialQueue.size;
        if (size > capacity()) {
            int newNumTrees = Math.max(trees.length, binomialQueue.trees.length) + 1;
            expandTrees(newNumTrees);
        }

        BinomialNode<T> carry = null;
        for (int i = 0, j = 1; j <= size; i++, j *= 2) {
            BinomialNode<T> t1 = trees[i];
            BinomialNode<T> t2 = i < binomialQueue.trees.length ? binomialQueue.trees[i] : null;

            int whichCase = t1 == null ? 0 : 1;
            whichCase += t2 == null ? 0 : 2;
            whichCase += carry == null ? 0 : 4;

            switch (whichCase) {
                case 0: /* No trees */
                case 1: /* Only this */
                    break;
                case 2: /* Only binomialQueue */
                    trees[i] = t2;
                    binomialQueue.trees[i] = null;
                    break;
                case 4: /* Only carry */
                    trees[i] = carry;
                    carry = null;
                    break;
                case 3: /* This and binomialQueue */
                    carry = combineTrees(t1, t2);
                    trees[i] = binomialQueue.trees[i] = null;
                    break;
                case 5: /* This and carry */
                    carry = combineTrees(t1, carry);
                    trees[i] = null;
                    break;
                case 6: /* BinomialQueue and carry */
                    carry = combineTrees(t2, carry);
                    binomialQueue.trees[i] = null;
                    break;
                case 7: /* All three */
                    trees[i] = carry;
                    carry = combineTrees(t1, t2);
                    binomialQueue.trees[i] = null;
                    break;
            }
        }

        for (int k = 0; k < binomialQueue.trees.length; k++) {
            binomialQueue.trees[k] = null;
        }
        binomialQueue.size = 0;
    }

    /**
     * Return the result of merging equal-sized tree1 and tree2.
     */
    private BinomialNode<T> combineTrees(BinomialNode<T> tree1, BinomialNode<T> tree2) {
        if (tree1.element.compareTo(tree2.element) > 0) {
            return combineTrees(tree2, tree1);
        }
        tree2.nextSibling = tree1.leftChild;
        tree1.leftChild = tree2;
        return tree1;
    }

    /**
     * Insert into the priority queue, maintaining heap order.
     * This implementation is not optimized for O(1) performance.
     *
     * @param x The item to insert.
     */
    public void insert(T x) {
        merge(new BinomialQueue<>(x));
    }

    /**
     * Find the smallest item in the priority queue.
     *
     * @return The smallest item, or throw exception if empty.
     */
    public T findMin() throws Exception {
        if (isEmpty()) {
            throw new Exception("Binomial queue is empty!");
        }

        return trees[findMinIndex()].element;
    }

    /**
     * Find index of tree containing the smallest item in the priority queue.
     * The priority queue must not be empty.
     *
     * @return The index of tree containing the smallest item.
     */
    private int findMinIndex() {
        int i;
        int minIndex;
        for (i = 0; trees[i] == null; i++) {
        }

        for (minIndex = i; i < trees.length; i++) {
            if (trees[i] != null && trees[i].element.compareTo(trees[minIndex].element) < 0) {
                minIndex = i;
            }
        }

        return minIndex;
    }

    /**
     * Remove the smallest item from the priority queue.
     *
     * @return The smallest item, or throw exception if empty.
     */
    public T deleteMin() throws Exception {
        if (isEmpty()) {
            throw new Exception("Binomial queue is empty!");
        }

        int minIndex = findMinIndex();
        T minItem = trees[minIndex].element;
        BinomialNode<T> deletedTree = trees[minIndex].leftChild;

        // Construct H''.
        BinomialQueue<T> deletedQueue = new BinomialQueue<>();
        deletedQueue.expandTrees(minIndex);
        deletedQueue.size = (1 << minIndex) - 1;
        for (int j = minIndex - 1; j >= 0; j--) {
            deletedQueue.trees[j] = deletedTree;
            deletedTree = deletedTree.nextSibling;
            deletedQueue.trees[j].nextSibling = null;
        }

        // Construct H'.
        trees[minIndex] = null;
        size -= deletedQueue.size + 1;
        merge(deletedQueue);

        return minItem;
    }

    /**
     * Test if the priority queue is logically empty.
     *
     * @return True if empty; false otherwise.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Make the priority queue logically empty.
     */
    public void makeEmpty() {
        size = 0;
        for (int i = 0; i < trees.length; i++) {
            trees[i] = null;
        }
    }

    /**
     * Return the capacity.
     */
    private int capacity() {
        return (1 << trees.length) - 1;
    }

    /**
     * Binomial queue node class.
     *
     * @param <AnyType> Any type.
     */
    private static class BinomialNode<AnyType> {
        AnyType element; // The data in the node.
        BinomialNode<AnyType> leftChild; // Left child.
        BinomialNode<AnyType> nextSibling; // Next sibling.

        // Constructors.
        BinomialNode(AnyType element) {
            this(element, null, null);
        }

        BinomialNode(AnyType element, BinomialNode<AnyType> leftChild, BinomialNode<AnyType> nextSibling) {
            this.element = element;
            this.leftChild = leftChild;
            this.nextSibling = nextSibling;
        }
    }
}

/*
Output:
Starting check.
Check done.

*/