Heap

HeapEntry.java

/
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(E element) {
		this.element = element;
    }

}

MaxHeap.java

import java.util.*;
/**
   Implements a heap with the reverse order of a minheap
*/
public class MaxHeap<E> {
    private MinHeap<E> theHeap; // used to store the items

    /* A comparator that imposes the reverse of the
       default ordering */
    private final  Comparator<E> REVERSE_COMPARATOR =
		new Comparator<E>() {
			public int compare(E lhs, E rhs) {
			return -  ((Comparable) lhs).compareTo(rhs);
			}
		};

    /**
     * Construct a maxheap using the reverse
     * of the natural ordering.
     */
    public MaxHeap() {
		theHeap = new MinHeap<E>(REVERSE_COMPARATOR);
    }

    /**
     * Construct a heap using the reverse
     *	ordering imposed by the comparator cmp
     *	@param cmp the Comparator to use
     */
    public MaxHeap (final Comparator<? super E> cmp) {
	/* reverse the order of cmp in order to store
	   items in the minheap theHeap */
		Comparator<E> reverse_Cmp =
			new Comparator<E>() {
				public int compare(E lhs, E rhs) {
					return - cmp.compare(lhs,rhs);
				}
			};
		theHeap = new MinHeap<E>(reverse_Cmp);
    }
	
	


    /**
     * Test if heap is logically empty.
     * @return true if empty; else false
     */       
    public boolean isEmpty() {

    }

    /**
     * Return number of items currently stored in the  heap.
     *  @return number of items stored in heap
     */
    public int size() {

    }

    /**
     *  Make heap logically empty.
     */
    public void makeEmpty() {

    }

    /**
     * Return largest item; null if heap is empty.
     *   @return largest item currently in heap; null if empty
     */
    public E findMax() {

    }

    /**
     * Insert item into the heap. Duplicates are allowed.
     * @param element the item to insert
     *  @return the entry containing the newly inserted item
     */
    public HeapEntry<E> insert(E element) {
	
    }

    /**
     * Delete and return the largest item of the heap;
     * null if empty.
     * @return the largest item; null if empty
     */
    public E deleteMax() {

    }

    /**
     * Change the value of the item stored in the heap.
     * @param entry the HeapEntry returned when item was inserted.
     * @param newVal the new value, which must be greater
     * than the currently stored value.
     * @throws RuntimeException if new value is smaller than old.
     */
    public void increaseKey(HeapEntry<E> b, E newVal)  {

    }

    /**
     * Change the value of the item stored in the heap.
     * @param entry the HeapEntry returned when item was inserted.
     * @param newVal the new value, which must be smaller
     * than the currently stored value.
     * @throws RuntimeException if new value is greaterer than old.
     */
    public void decreaseKey(HeapEntry<E> b, E newVal)  {

    }
}

MinHeap.java

import java.util.*;

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 number of items currently stored in the  heap.
     * @return number of items stored in heap
     */
    public int size() {

    }

    /**
     * Make heap logically empty.
     */
    public void makeEmpty() {

    }

    /**
     * Return smallest item; null if heap is empty.
     * @return smallest item currently in heap; null if empty
     */
    public E findMin() {
	if (isEmpty())
	    return null;
	else
	    return theArray[1].element;
    }

   
    /**
     * Insert item into the heap. Duplicates are allowed.
     * @param element the item to insert
     * @return the entry containing the newly inserted item
     */
    public HeapEntry<E> insert(E element) {

    }

    /**
     * Delete and return the smallest item of the heap;
     * null if empty.
     * @return the smallest item; null if empty
     */
    public E deleteMin() {

    }

    /**
     * Change the value of the item stored in the heap.
     * @param entry the HeapEntry returned when item was inserted.
     * @param newVal the new value, which must be smaller
     * than the currently stored value.
     * @throws RuntimeException if new value is larger than old.
     */
    public void decreaseKey(HeapEntry<E> entry, E newVal) {
	
    }

    /**
     * Change the value of the item stored in the heap.
     * @param entry the HeapEntry returned when item was inserted.
     * @param newVal the new value, which must be greater
     * than the currently stored value.
     * @throws RuntimeException if new value is smaller than old.
     */
    public void increaseKey(HeapEntry<E> entry, E newVal) {
	
    }

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

    }
    

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

    /*
     * 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 weiss.util.Random;

import java.util.*;

/**
 * This class tests BinaryHeap
 */
public class TestMinHeap extends TestCase {
    private MinHeap<Integer> myHeap;
    private Integer[] intArray;

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

    /**
     * This method is executed prior to each test.
     * myHeap is initialized to an empty heap
     * and test-objects to insert are created .
     */
    protected void setUp() {
		myHeap = new MinHeap<Integer>();
		intArray = new Integer[10];
		for (int i=0; i<10;i++)
			intArray[i] = new Integer(i);	
    }

    /**
      * This method is executed after each test.
      *	The reference to the created heap is cleared.
      */
    protected void tearDown() {
		myHeap  = null;
    }

    /**
     * Test if a newly created heap is empty.
     */
    public void testNewHeap() {
		assertTrue(myHeap.isEmpty());
    }

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

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

  
    /**
     * Test findMin after several insertions
     */
    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);
    }
}