CSC212 Homework 7 2014

--D. Thiebaut (talk) 09:51, 3 November 2014 (EST)

---

The program is due on Friday, Nov. 14, at 11:55 p.m.

Problem #1

Look at this javadoc document; it is the javadoc (pdf) of the program you have to implement. It is a heap implemented with an ArrayList of ints.

• You have to reconstruct it, including all its method, and call the class Heap.java.
• You will notice that the pop() method returns the top of the heap, but if the heap is empty, it raises an exception of type HeapEmptyException. Its definition is given below. You should create a separate java file for it, and call it HeapEmptyException.java. Your program will automatically find it if you declare it in the same Eclipse package.

public class HeapEmptyException extends Exception{
    //Parameterless Constructor
    public HeapEmptyException() {}

    //Constructor that accepts a message
    public HeapEmptyException(String message){
       super(message);
    }
}

Getting Started

• Here is a main() program you can use for your heap to start testing it out. Feel free to add more tests as you develop it.

	public static void main(String[] args) {
		Heap heap = new Heap();
		int[] keys = new int[] { 3, 100, 10, 5, 5, 5, 20, 5, 12, 40, 2, 100 };
		
		System.out.println( "Heap empty status: " + heap.isEmpty() );
		
		for ( int i=0; i<keys.length; i++ ) {
			heap.insert( keys[i] );
			System.out.println( "After inserting "+ keys[i] + ": " 
					+ heap + " -- size = " + heap.size()  );
		}
		//heap.swap( 1,  3 );
		//System.out.println( "After swapping "+ keys[1] + " and " + keys[3] + ": " + heap );

		while ( ! heap.isEmpty() ) {
			int root = heap.getTop();
			System.out.println( "heap after deleting " + root + ": " 
					+ heap +" -- size = " + heap.size() );
		}	
	}

• Here's the output of the main() function you should get with your heap:

Heap empty status: true
After inserting 3: [3] -- size = 1
After inserting 100: [100, 3] -- size = 2
After inserting 10: [100, 3, 10] -- size = 3
After inserting 5: [100, 5, 10, 3] -- size = 4
After inserting 5: [100, 5, 10, 3, 5] -- size = 5
After inserting 5: [100, 5, 10, 3, 5, 5] -- size = 6
After inserting 20: [100, 5, 20, 3, 5, 5, 10] -- size = 7
After inserting 5: [100, 5, 20, 5, 5, 5, 10, 3] -- size = 8
After inserting 12: [100, 12, 20, 5, 5, 5, 10, 3, 5] -- size = 9
After inserting 40: [100, 40, 20, 5, 12, 5, 10, 3, 5, 5] -- size = 10
After inserting 2: [100, 40, 20, 5, 12, 5, 10, 3, 5, 5, 2] -- size = 11
After inserting 100: [100, 40, 100, 5, 12, 20, 10, 3, 5, 5, 2, 5] -- size = 12
heap after deleting 100: [100, 40, 20, 5, 12, 5, 10, 3, 5, 5, 2] -- size = 11
heap after deleting 100: [40, 12, 20, 5, 5, 5, 10, 3, 5, 2] -- size = 10
heap after deleting 40: [20, 12, 10, 5, 5, 5, 2, 3, 5] -- size = 9
heap after deleting 20: [12, 5, 10, 5, 5, 5, 2, 3] -- size = 8
heap after deleting 12: [10, 5, 5, 5, 5, 3, 2] -- size = 7
heap after deleting 10: [5, 5, 5, 2, 5, 3] -- size = 6
heap after deleting 5: [5, 5, 5, 2, 3] -- size = 5
heap after deleting 5: [5, 3, 5, 2] -- size = 4
heap after deleting 5: [5, 3, 2] -- size = 3
heap after deleting 5: [3, 2] -- size = 2
heap after deleting 3: [2] -- size = 1
heap after deleting 2: [] -- size = 0

Additional Information

• The javadoc contains only the public methods. Not the private method.
• My heap program contains several private methods. I'm including them here to help out. Because they are private, they are not available to the outside world, and my test program will not be able to call them. For this reason, you do not have to follow the same choices I have made, and you may want to call them differently, or even pass different parameters to them. The choice is yours. This is just provided as helpful hints. You are free not to use and not to follow the hints.

/**
	 * heapifyUP: given the index of a node in the heap, moves node up
	 * if necessary to establish heap property back.
	 * @param index: the index of the node currently processed.
	 */
	protected void heapifyUp( int index ) {...}

	/**
	 * heapifyDown: given the index of a node in the heap (implemented by an arrayList)
	 * swap the node with the child with the largest key if necessary, in order to maintain
	 * the heap property.  Recurses on the child just swapped.
	 * @param index is the index of the node being considered.
	 */
	protected void heapifyDown(int index ) {...}