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?
