Heap (rev 2)

Heap.java

// Programvaruutveckling i Grupp, Spike 01 - 1/19/2007

public class Heap {

	public static void main(String[] args) {
		
		Integer[] intArray;
		
		MinHeap<Integer> myHeap = new MinHeap<Integer>();
		
		// Insert elements in heap (random values)
		
		intArray = new Integer[10];
		
		System.out.println("Inserting elements in heap:\n==============================");
		
		for (int i=0; i<10;i++) {
			
			intArray[i] = new Integer((int)(Math.random()*(double)(i+1)*100));
			myHeap.insert(intArray[i]);
			System.out.println(intArray[i]);
		}
		
		
		// Get min-elements from heap
		
		Integer minElement = myHeap.findMin();
		
		System.out.println("\nRetrieving elements from heap:\n==============================");
		while(!myHeap.isEmpty()) {
			
			System.out.println(myHeap.deleteMin());
		}	
	}	
}

HeapEntry.java

// Generic HeapEntry class

public class HeapEntry<E> {
	
    E element;	   // element associated with this HeapEntry object
    int index;     // index of this HeapEntry object in the array
                   // representing the heap.

    // HeapEntry constructor (non-public contructor)
    HeapEntry(E element) {
		this.element = element;
    }
}

MinHeap.java

import java.util.*;

// Generic Implementation of MinHeap datastructure

public class MinHeap<E> {

    private HeapEntry<E>[] theArray;	// array to store items in heap
    private Comparator<? super E> cmp;  // the comparator used for matching items
    private int currentSize;		// current number of items stored
    
    private final static int DEFAULT_CAPACITY = 100; // initial capacity of the heap

    // A comparator using the natural ordering (Comparable)
    private final Comparator<E> DEFAULT_COMPARATOR =

	new Comparator<E>() {
    	
		    public int compare(E lhs, E rhs) {
		    	return( (Comparable) lhs).compareTo(rhs);
		    }
	};  
       
    public MinHeap() {

		theArray = (HeapEntry<E>[]) new HeapEntry[DEFAULT_CAPACITY + 1];
		currentSize = 0;
		cmp = DEFAULT_COMPARATOR;

    }

    public MinHeap(Comparator<? super E> cmp) {

		this();
		this.cmp = cmp;
    }

    public boolean isEmpty() {
		
		return currentSize == 0;
    }

    public int size() {

		return currentSize;
    }

   
    public void makeEmpty() {
		
		currentSize = 0;
    }

    public E findMin() {

		if (isEmpty())
			return null;
		else
			return theArray[1].element;
    }
    
    public HeapEntry<E> insert(E element) {

		if(currentSize + 1 == theArray.length)
			doubleArray();

		HeapEntry he = new HeapEntry(element);

		int hole = ++currentSize;
		theArray[hole] = he;
		he.index = hole;	
		
		if(currentSize > 1)
			percolateUp(he);

		return he;
    }

    public E deleteMin() {

		E ret=null;

		if (currentSize >= 1) {

			ret = theArray[1].element;
			theArray[1] = theArray[currentSize];
			theArray[1].index = 1;
			currentSize--;
			if (currentSize >= 2) percolateDown(theArray[1]);
		}

		return ret;

    }
    
    public void decreaseKey(HeapEntry<E> entry, E newVal) {

		if(cmp.compare(entry.element,newVal) < 0)
			throw new RuntimeException();

		changeKey(entry, newVal);
    }

    public void increaseKey(HeapEntry<E> entry, E newVal) {

		if(cmp.compare(entry.element,newVal) > 0)
			throw new RuntimeException();

		changeKey(entry, newVal);
    }


   
    // Delete the HeapEntry h from the heap.
   
    public void delete(HeapEntry<E> h) {

		theArray[h.index] = theArray[currentSize];
		theArray[h.index].index = h.index;
		currentSize--;
		percolateUpOrDown(h.index);	
    }

    // ---------------- private methods ----------------

	// Move an item up to its correct position	
    private void percolateUp(HeapEntry heap) 
	{
       
		while(cmp.compare((E)heap.element, theArray[heap.index / 2].element) < 0) {

			theArray[heap.index] = theArray[heap.index / 2];
			theArray[heap.index].index = heap.index;

			heap.index /= 2;
				if(heap.index == 1) break;

		}

		theArray[heap.index] = heap;
    }
	
	// Move an item down to its correct position	
    private void percolateDown(HeapEntry heap) 
	{
		int child;
		int hole = heap.index;

		for ( ; hole * 2 <= currentSize; hole = child) {
			
			child = hole * 2;

			if (child != currentSize && cmp.compare((E)theArray[child+1].element, theArray[child].element) < 0 ) 
				child++;

			if(cmp.compare((E)theArray[child].element, (E)heap.element) < 0) {
				theArray[hole] = theArray[child];
         			theArray[hole].index = hole;
			}
			else
			break;
		}

		theArray[hole] = heap;
		heap.index = hole;
	}
	
	// Internal method to choose between percolate up or down	
	private void percolateUpOrDown(int index) 
	{
		if(currentSize > 1) {
			if (index * 2 <= currentSize) {

				if (cmp.compare((E)theArray[index].element, theArray[index * 2].element) > 0) 
					percolateDown(theArray[index]);
				else if (index * 2 + 1 <= currentSize )
					if (cmp.compare((E)theArray[index].element, theArray[index * 2 + 1].element) > 0) 
					percolateDown(theArray[index]);
			}
			else if (cmp.compare((E)theArray[index].element, theArray[index / 2].element) < 0)
				percolateUp(theArray[index]);
		}
    }
	
	// Internal method to change the key	
    private void changeKey(HeapEntry<E> entry, E newVal) 
	{	
		entry.element = newVal;
		percolateUpOrDown(entry.index);
    }

	// Internal method to extend the array.	
    private void doubleArray() {

		HeapEntry<E> [] temp = (HeapEntry<E>[]) new HeapEntry[2*theArray.length];
		for (int i = 0; i < theArray.length; i++)
			temp[i] = theArray[i];
		theArray = temp;
    } 
}

TestMinHeap.java

import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;

import java.util.*;

// Some JUnit tests for MinHeap class

public class TestMinHeap extends TestCase {
    private MinHeap<Integer> myHeap;
    private Integer[] intArray;

    public TestMinHeap(String name) {
		super(name);
    }

    protected void setUp() {
		myHeap = new MinHeap<Integer>();
		intArray = new Integer[10];
		for (int i=0; i<10;i++)
			intArray[i] = new Integer(i);	
    }

    protected void tearDown() {
		myHeap  = null;
    }

    public void testNewHeap() {
		assertTrue(myHeap.isEmpty());
    }

    public void testEmptyFindMin() {
		assertEquals("findMin-error on empty heap", myHeap.findMin(),null);
    }

    public void testFindMinAfterSingleInsert() {
		myHeap.insert(intArray[9]);
		assertEquals("findMin-error on single element heap", myHeap.findMin(),intArray[9]);
    }

    public void testFindMinAfterManyInserts() {
		myHeap.insert(intArray[4]);
		myHeap.insert(intArray[9]);
		myHeap.insert(intArray[6]);
		myHeap.insert(intArray[0]);
		myHeap.insert(intArray[1]);
		assertEquals("findMin-error after several inserts", myHeap.findMin(),intArray[0]);
    }
       
    public static void main(String[] args) {
		junit.swingui.TestRunner.run(TestMinHeap.class);
    }
}