BinaryHeap

BinaryHeap.java

import java.util.NoSuchElementException;

/**
 * A binary heap is a heap data structure create using a binary tree.
 * 
 * @author Takanori Ishikawa <[email protected]>
 */
public class BinaryHeap<E extends Comparable<E>> {
	
	private E[] items;
	private int size;
	
	public BinaryHeap(int capacity) {
		items = (E[]) new Comparable[capacity]; // ugly, but working
	}

	public int size() {
		return size;
	}

	public int capacity() {
		return items.length;
	}

	public boolean add(E e) {
		if (!offer(e)) throw new IllegalStateException();
		return true;
	}

	public boolean offer(E e) {
		if (size >= items.length) return false;
		items[size++] = e;
		shiftup();
		return true;
	}
	
	public E element() {
		final E e = peek();
		if (e == null) throw new NoSuchElementException();
		return e;
	}
	
	public E peek() {
		return size == 0 ? null : items[0];
	}

	public E remove() {
		final E e = poll();
		if (e == null) throw new NoSuchElementException();
		return e;
	}
	
	public E poll() {
		if (size == 0) return null;
		final E e = items[0];
		items[0] = items[--size];
		shiftdown();
		return e;
	}

	private void swap(int i, int j) {
		final E e = items[j];
		items[j] = items[i];
		items[i] = e;
	}

	private void shiftup() {
		int i = size - 1;
		while (i > 0) {
			final int p = (i+1)/2-1;
			if (items[i].compareTo(items[p]) >= 0) break;
			swap(i, p);
			i = p;
		}
	}

	private void shiftdown() {
		int i = 0;
		while(i < size) {
			int c = (i+1)*2-1; // left child
			if (c > size) break;
			if ((c+1) < size && items[c+1].compareTo(items[c]) < 0) c++;
			if (items[i].compareTo(items[c]) <= 0) break;
			swap(i, c);
			i = c;
		}
	}

}

BinaryHeapTest.java

import junit.framework.TestCase;

public class BinaryHeapTest extends TestCase {

	public void test_init() {
		BinaryHeap<Integer> heap = new BinaryHeap<Integer>(1);
		assertNotNull(heap);
		assertEquals(0, heap.size());
		assertEquals(1, heap.capacity());
	}

	public void test_one_element() {
		BinaryHeap<Integer> heap = new BinaryHeap<Integer>(8);
		
		assertEquals(0, heap.size());
		assertEquals(8, heap.capacity());
		
		heap.add(1);
		assertEquals(1, heap.size());
		assertEquals(new Integer(1), heap.peek());
		assertEquals(new Integer(1), heap.element());
		assertEquals(new Integer(1), heap.remove());
		assertEquals(0, heap.size());
	}

	public void test_elements() {
		BinaryHeap<Integer> heap = new BinaryHeap<Integer>(5);
		assertEquals(0, heap.size());
		assertEquals(5, heap.capacity());

		// add
		heap.add(20);
		heap.add(5);
		heap.add(19);
		heap.add(1);
		heap.add(27);
		assertEquals(5, heap.size());
		
		// peek
		assertEquals(new Integer(1), heap.peek());
		assertEquals(5, heap.size());
		
		// remove
		assertEquals(new Integer(1), heap.remove());
		assertEquals(4, heap.size());
		assertEquals(new Integer(5), heap.remove());
		assertEquals(3, heap.size());
	}

	public void test_reversed() {
		BinaryHeap<Integer> heap = new BinaryHeap<Integer>(5);
		assertEquals(0, heap.size());
		assertEquals(5, heap.capacity());

		// add
		heap.add(5);
		heap.add(4);
		heap.add(3);
		heap.add(2);
		heap.add(1);
		assertEquals(5, heap.size());
		
		// peek
		assertEquals(new Integer(1), heap.peek());
		assertEquals(5, heap.size());
		
		// remove
		assertEquals(new Integer(1), heap.remove());
		assertEquals(4, heap.size());
		assertEquals(new Integer(2), heap.remove());
		assertEquals(3, heap.size());
		assertEquals(new Integer(3), heap.remove());
		assertEquals(2, heap.size());
		assertEquals(new Integer(4), heap.remove());
		assertEquals(1, heap.size());
		assertEquals(new Integer(5), heap.remove());
		assertEquals(0, heap.size());
		
	}
}