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 };
		
		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:

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