2
\$\begingroup\$

I have this implementation of a binomial heap providing insert, decrease-key and extract in logarithmic time.

MinPriorityQueue.java:

package com.stackexchange.codereview.ds;

/**
 * This abstract class defines the API for the various minimum-priority queue
 * data structures.
 * 
 * @author Rodion Efremov
 * @param <E> the type of elements stored by the implementation.
 * @param <P> the type of the priority keys.
 * @version 1.6
 */
public abstract class MinPriorityQueue<E, P extends Comparable<? super P>> {

    /**
     * Adds <code>element</code> and assigns to it the priority 
     * <code>priority</code>.
     * 
     * @param element  the element to store.
     * @param priority the priority of the element.
     */
    public abstract void add(final E element, final P priority);

    /**
     * Decreases the priority of the element <code>element</code> if it is 
     * present. If the element is not in this heap, or new priority does not
     * improve the current priority, does nothing.
     * 
     * @param element     the element whose priority to decrease.
     * @param newPriority the new priority of <code>element</code>.
     */
    public abstract void decreasePriority(final E element, final P newPriority);

    /**
     * Extracts the element with the lowest priority.
     * 
     * @return the element with the lowest priority.
     * 
     * @throws java.util.NoSuchElementException if the heap is empty.
     */
    public abstract E extractMinimum();

    /**
     * Returns but does not remove the minimum element.
     * 
     * @return the minimum element. 
     */
    public abstract E min();

    /**
     * Returns the amount of elements in the heap.
     * 
     * @return the amount of elements in the heap. 
     */
    public abstract int size();

    /**
     * Returns <code>true</code> it this heap is empty. <code>false</code> 
     * otherwise.
     * 
     * @return <code>true</code> or <code>false</code>.
     */
    public abstract boolean isEmpty();

    /**
     * Removes all elements from this heap.
     */
    public abstract void clear();

    /**
     * Spawns another empty heap with the same implementation.
     * 
     * @return another empty heap.
     */
    public abstract MinPriorityQueue<E, P> spawn();

    /**
     * Returns a string indicating the actual implementation type.
     * 
     * @return a string indicating implementation type.
     */
    @Override
    public abstract String toString();
}

BinomialHeap.java:

package com.stackexchange.codereview.ds.support;

import com.stackexchange.codereview.ds.MinPriorityQueue;
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * This class implements binomial heap.
 * 
 * @author Rodion Efremov
 * @version 1.6
 * @param <E> the element type.
 * @param <P> the type of priority keys.
 */
public class BinomialHeap<E, P extends Comparable<? super P>>
extends MinPriorityQueue<E, P> {

    /**
     * The default map capacity.
     */
    private static final int DEFAULT_MAP_CAPACITY = 1 << 10;

    /**
     * This class implements a binomial tree in a binomial heap.
     * 
     * @param <E> the element type.
     * @param <P> the type of priority keys.
     */
    private static final class BinomialTree<E, P> {

        /**
         * The actual element of this node.
         */
        E element;

        /**
         * The priority key of this node.
         */
        P priority;

        /**
         * The parent node.
         */
        BinomialTree<E, P> parent;

        /**
         * Immediate sibling of this node to the right.
         */
        BinomialTree<E, P> sibling;

        /**
         * The leftmost child of this node.
         */
        BinomialTree<E, P> child;

        /**
         * The amount of children of this node.
         */
        int degree;

        /**
         * Constructs a new node and initialize it with mandatory data.
         * 
         * @param element  the element to store in this node.
         * @param priority the priority of the element stored.
         */
        BinomialTree(E element, P priority) {
            this.element = element;
            this.priority = priority;
        }
    }

    /**
     * Caches the amount of elements in this binomial heap.
     */
    private int size;

    /**
     * Points to the leftmost node in the root list of this heap.
     */
    private BinomialTree<E, P> head;

    /**
     * Caches the binomial tree with the least priority key.
     */
    private BinomialTree<E, P> minimumTree;

    /**
     * Maps each element in the heap to its respective node.
     */
    private final Map<E, BinomialTree<E, P>> map;

    /**
     * Constructs a new {@code BinomialHeap} with default settings.
     */
    public BinomialHeap() {
        this(DEFAULT_MAP_CAPACITY);
    }

    /**
     * Constructs a new {@code BinomialHeap} using <code>mapCapacity</code> as 
     * the initial capacity for the underlying map.
     * 
     * @param mapCapacity the initial map capacity.
     */
    public BinomialHeap(final int mapCapacity) {
        this.map = new HashMap<>(mapCapacity);
    }

    /**
     * Constructs a binomial heap with only one element. Used for the sake of 
     * <code>add</code>-operation, which simply unites the current heap with the
     * one created by this constructor.
     * 
     * @param element the application-specific satellite data.
     * @param priority the priority of <code>element</code>.
     */
    private BinomialHeap(final E element, final P priority) {
        BinomialTree<E, P> tree = new BinomialTree<>(element, priority);
        head = tree;
        minimumTree = tree;
        size = 1;
        map = null;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void add(E element, P priority) {
        if (map.containsKey(element)) {
            // element already in this heap, use decreaseKey instead.
            return;
        }

        BinomialHeap<E, P> h = new BinomialHeap<>(element, priority);

        if (size == 0) {
            this.head = h.head;
            this.minimumTree = h.head;
            this.map.put(element, this.head);
            this.size = 1;
        } else {
            heapUnion(h.head);
            this.map.put(element, h.head);
            this.size++;

            if (minimumTree.priority.compareTo(h.minimumTree.priority) > 0) {
                minimumTree = h.minimumTree;
            }
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void decreasePriority(E element, P newPriority) {
        if (!map.containsKey(element)) {
            // No element here.
            return;
        } 

        BinomialTree<E, P> target = map.get(element);

        if (target.priority.compareTo(newPriority) <= 0) {
            // The priority key of element won't improve.
            return;
        }

        final E saveElement = target.element;

        BinomialTree<E, P> p = target.parent;
        BinomialTree<E, P> x = target;

        while (p != null && newPriority.compareTo(p.priority) < 0) {
            x.priority = p.priority;
            x.element = p.element;

            // Advance one level up.
            x = p;
            p = p.parent;
        }

        x.element = saveElement;
        x.priority = newPriority;

        if (minimumTree.priority.compareTo(x.priority) > 0) {
            minimumTree = x;
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public E extractMinimum() {
        if (size == 0) {
            throw new NoSuchElementException(
                    "Reading from an empty binomial heap.");
        }

        BinomialTree<E, P> x = head;
        BinomialTree<E, P> prevx = null;
        BinomialTree<E, P> best = x;
        BinomialTree<E, P> bestprev = null;
        P minPriorityKey = x.priority;

        // Find the tree T with the least priority element and the tree 
        // preceding T.
        while (x != null) {
            if (minPriorityKey.compareTo(x.priority) > 0) {
                minPriorityKey = x.priority;
                best = x;
                bestprev = prevx;
            }

            prevx = x;
            x = x.sibling;
        }

        // Remove from root list the tree with the least priority root.
        if (bestprev == null) {
            head = best.sibling;
        } else {
            bestprev.sibling = best.sibling;
        }

        // Unite this heap with the reversed list of children of the tree whose
        // root contained the extracted element.
        heapUnion(reverseRootList(best.child));

        // Update the cached minimum tree.
        if (--size > 0) {
            BinomialTree<E, P> minTree = head;
            BinomialTree<E, P> t = head.sibling;
            P minPriority = head.priority;

            while (t != null) {
                if (minPriority.compareTo(t.priority) > 0) {
                    minPriority = t.priority;
                    minTree = t;
                }

                t = t.sibling;
            }

            minimumTree = minTree;
        }

        return best.element;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public E min() {
        if (size == 0) {
            throw new NoSuchElementException("Reading from an empty heap.");
        }

        return minimumTree.element;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void clear() {
        this.head = null;
        this.map.clear();
        this.size = 0;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public MinPriorityQueue<E, P> spawn() {
       return new BinomialHeap<>();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public String toString() {
        return "BinomialHeap";
    }

    /**
     * Makes <code>y</code> a leftmost child of <code>z</code>.
     * 
     * @param y the node to become a child of <code>z</code>.
     * @param z the node to become a parent of <code>y</code>.
     */
    private void link(final BinomialTree<E, P> child, 
                      final BinomialTree<E, P> parent) {
        child.parent = parent;
        child.sibling = parent.child;
        parent.child = child;
        parent.degree++;
    }

    /**
     * Merges the root lists of this heap and <code>other</code>.
     * 
     * @param other another binomial heap whose root list to merge.
     * 
     * @return the head of the merged root list. 
     */
    private BinomialTree<E, P> mergeRoots(final BinomialTree<E, P> other) {
        BinomialTree<E, P> a = head;
        BinomialTree<E, P> b = other;

        if (a == null) {
            return b;
        } else if (b == null) {
            return a;
        }

        BinomialTree<E, P> rootListHead;
        BinomialTree<E, P> rootListTail;

        // Initialize rootListHead and rootListTail.
        if (a.degree < b.degree) {
            rootListHead = a;
            rootListTail = a;
            a = a.sibling;
        } else {
            rootListHead = b;
            rootListTail = b;
            b = b.sibling;
        }

        while (a != null && b != null) {
            if (a.degree < b.degree) {
                rootListTail.sibling = a;
                rootListTail = a;
                a = a.sibling;
            } else {
                rootListTail.sibling = b;
                rootListTail = b;
                b = b.sibling;
            }
        }

        if (a != null) {
            // Just append the rest.
            rootListTail.sibling = a;
        } else {
            // Just append the rest.
            rootListTail.sibling = b;
        }

        return rootListHead;
    }

    /**
     * Reverses the root list as to facilitate the <code>extractMinimum</code>.
     * Sets the parent references to <code>null</code> also.
     * 
     * @param first the head node of the root list to reverse.
     * 
     * @return the reversed root list. 
     */
    private BinomialTree<E, P> reverseRootList(final BinomialTree<E, P> first) {
        BinomialTree<E, P> tmp = first; // This is the cursor over the list.
        BinomialTree<E, P> tmpnext;
        BinomialTree<E, P> newHead = null;

        while (tmp != null) {
            tmpnext = tmp.sibling;
            tmp.sibling = newHead;
            newHead = tmp;
            tmp = tmpnext;
        }

        return newHead;
    }

    /**
     * Unites this heap with <code>other</code>. This subroutine is used in both
     * <code>add</code> and <code>extractMinimum</code>.
     * 
     * @param other the heap to unite with this heap. 
     */
    private void heapUnion(final BinomialTree<E, P> other) {
        if (other == null) {
            return;
        }

        BinomialTree<E, P> t = mergeRoots(other);
        BinomialTree<E, P> prev = null;
        BinomialTree<E, P> x = t;
        BinomialTree<E, P> next = x.sibling;

        while (next != null) {
            if ((x.degree != next.degree)
                    || (next.sibling != null 
                    && next.sibling.degree == x.degree)) {
                prev = x;
                x = next;
            } else if (x.priority.compareTo(next.priority) <= 0) {
                x.sibling = next.sibling;
                link(next, x);
            } else {
                if (prev == null) {
                    t = next;
                } else {
                    prev.sibling = next;
                }

                link(x, next);
                x = next;
            }

            next = x.sibling;
        }

        this.head = t;
    }
}

Demo.java:

package com.stackexchange.codereview.ds;

import com.stackexchange.codereview.ds.support.BinomialHeap;

public class Demo {

    private static final int TO_LOAD = 100000;

    public static void main(final String... args) {
        final MinPriorityQueue<Integer, Integer> heap = new BinomialHeap<>();

        long ta = System.currentTimeMillis();

        for (int i = 0; i < TO_LOAD; ++i) {
            heap.add(i, i);
        }

        long tb = System.currentTimeMillis();

        System.out.println("add() in " + (tb - ta) + " ms.");

        ta = System.currentTimeMillis();

        for (int i = TO_LOAD / 2; i < TO_LOAD; ++i) {
            heap.decreasePriority(i, i - TO_LOAD);
        }

        tb = System.currentTimeMillis();

        System.out.println("decreasePriority() in " + (tb - ta) + " ms.");

        boolean isCorrect = true;

        ta = System.currentTimeMillis();

        for (int i = 0; i < TO_LOAD - TO_LOAD / 2; ++i) {
            if (!heap.extractMinimum().equals(i + TO_LOAD / 2)) {
                isCorrect = false;
                System.out.println("1");
                break;
            }
        }

        if (isCorrect) {
            for (int i = 0; i < TO_LOAD / 2; ++i) {
                if (!heap.extractMinimum().equals(i)) {
                    System.out.println("2");
                    isCorrect = false;
                    break;
                }
            }
        }

        tb = System.currentTimeMillis();

        System.out.println("extractMinimum() in " + (tb - ta) + " ms.");

        System.out.println("Is correct: " + isCorrect);
    }
}

BinomialHeapTest.java:

package com.stackexchange.codereview.ds.support;

import java.util.NoSuchElementException;
import java.util.Random;
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;

public class BinomialHeapTest {

    private static final long seed = System.currentTimeMillis();

    private final BinomialHeap<Integer, Integer> heap;

    public BinomialHeapTest() {
        this.heap = new BinomialHeap<>();
    }

    @BeforeClass
    public static void initClass() {
        System.out.println("BinomialHeapTest.java, seed: " + seed);
    }

    /**
     * Clears the heap before any test.
     */
    @Before
    public void init() {
        heap.clear();
    }

    @Test
    public void testAddAndExtractMinimum() {
        final int sz = 100000;
        final Random rnd = new Random(seed);

        for (int i = 0; i != sz; ++i) {
            Integer ii = rnd.nextInt();
            heap.add(ii, ii);
        }

        Integer prev = null;

        while (!heap.isEmpty()) {
            Integer current = heap.extractMinimum();

            if (prev != null && prev > current) {
                fail("The sequence was not monotonically increasing. " +
                     "Previous: " + prev + ", current: " + current + ".");
            }

            prev = current;
        }
    }

    @Test
    public void testDecreasePriority() {
        for (int i = 10; i != 0; --i) {
            heap.add(i, i);
        }

        heap.decreasePriority(10, -1);

        assertEquals((Integer) 10, heap.extractMinimum());

        int i = 1;
        while (!heap.isEmpty()) {
            assertEquals((Integer) i, heap.extractMinimum());
            i++;
        }
    }

    @Test
    public void testSize() {
        assertTrue(heap.isEmpty());

        final long sz = 10000;

        for (int i = 0; i < sz; ++i) {
            assertEquals(i, heap.size());
            heap.add(i, i);
        }

        assertEquals(sz, heap.size());
        assertFalse(heap.isEmpty());
    }

    @Test
    public void testIsEmpty() {
        assertTrue(heap.isEmpty());

        heap.add(0, 0);

        assertFalse(heap.isEmpty());

        heap.add(1, -1);

        assertFalse(heap.isEmpty());

        heap.extractMinimum();

        assertFalse(heap.isEmpty());

        heap.extractMinimum();

        assertTrue(heap.isEmpty());

        heap.add(100, 10);
        heap.add(10, 1);

        assertFalse(heap.isEmpty());

        heap.clear();

        assertTrue(heap.isEmpty());
    }

    @Test
    public void testClear() {
        assertTrue(heap.isEmpty());

        final int sz = 10000;

        for (int i = 0; i < sz; ++i) {
            heap.add(i, i);
            assertFalse(heap.isEmpty());
        }

        heap.clear();

        assertTrue(heap.isEmpty());
        assertEquals(0, heap.size());
    }

    @Test
    public void testSpawn() {
        heap.add(1, 2);

        BinomialHeap<Integer, Integer> heap2 = 
                (BinomialHeap<Integer, Integer>) heap.spawn();

        assertTrue(heap2 instanceof BinomialHeap);
        assertFalse(heap.isEmpty());
        assertTrue(heap2.isEmpty());
    }

    /**
     * Additional test.
     */
    @Test
    public void additionalTest() {
        heap.add(2, 2);
        heap.add(1, 1);
        heap.add(3, 7);
        heap.add(4, 6);
        heap.decreasePriority(3, -1);
        heap.decreasePriority(4, 10);
        heap.add(4, -4);

        assertEquals(4, heap.size());
        assertFalse(heap.isEmpty());

        assertEquals((Integer) 3, heap.extractMinimum());
        assertEquals((Integer) 1, heap.extractMinimum());
        assertEquals((Integer) 2, heap.extractMinimum());
        assertEquals((Integer) 4, heap.extractMinimum());

        assertTrue(heap.isEmpty());
        assertEquals(0, heap.size());
    }

    @Test(expected = NoSuchElementException.class)
    public void testExtractingFromEmptyThrows() {
        heap.add(10, 10);
        heap.add(1, 29);

        heap.extractMinimum();
        heap.extractMinimum();
        heap.extractMinimum();
    }

    @Test(expected = NoSuchElementException.class)
    public void testPeekingEmptyHeapThrows() {
        heap.min();
    }

    @Test
    public void testMin() {
        heap.add(3, 3); // (3, 3)

        assertEquals((Integer) 3, heap.min());

        heap.add(2, 2); // (2, 2) (3, 3)

        assertEquals((Integer) 2, heap.min());

        assertEquals(2, heap.size());

        heap.decreasePriority(3, 1); // (3, 1) (2, 2)

        assertEquals((Integer) 3, heap.min());

        assertEquals(2, heap.size());

        assertEquals((Integer) 3, heap.extractMinimum()); // (2, 2)

        assertEquals(1, heap.size());

        assertEquals((Integer) 2, heap.min());

        assertEquals((Integer) 2, heap.extractMinimum());

        assertEquals(0, heap.size());

        try {
            heap.min();
            fail("BinomialHeap did not throw on being read while empty.");
        } catch (final NoSuchElementException nsee) {

        }
    }
}

So what do you think?

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

At first glance, I see some issues with the interface.

MinPriorityQueue is an abstract class that contains no instructions. It would be better as an interface instead. In that case, neither spawn() nor toString() would be part of that interface. If you wanted to support spawn(), then make a separate Spawnable<T> interface. And your toString() is pointless — not only do all objects in Java support toString(), your implementation, which just returns "BinomialHeap", is arguably less useful than the usual BinomialHeap@56e88e24 that Java gives you. If you hadn't declared toString() to be abstract, you could have gotten the default behaviour for free.


I find this behaviour troubling:

public void add(E element, P priority) {
    if (map.containsKey(element)) {
        // element already in this heap, use decreaseKey instead.
        return;
    }
    …
}

If someone tries to add an element that is already present, I would consider the following possible behaviours reasonable (from best to weirdest, in my opinion):

  1. Add a second instance of the same element (list-like semantics).
  2. Throw an exception
  3. Return false if the element was not added because it already exists (java.util.Set-like semantics)
  4. Reprioritize the existing entry

Silently doing nothing is not acceptable, in my opinion.

An analogous problem exists in decreasePriority():

public void decreasePriority(E element, P newPriority) {
    if (!map.containsKey(element)) {
        // No element here.
        return;
    } 
    …
}

There, my expectation would be to throw an exception if no such element exists.


Since your BinomialHeap uses a map, you might as well offer a .contains(E) method.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I need the hash map in order to keep decreasePriority an O(log n) operation. Otherwise, I would need to traverse the entire heap to find the node containing the element, and that's O(n). \$\endgroup\$
    – coderodde
    Jan 11, 2015 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.