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 methods.
• 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 ) {...}

• Often java libraries provide two different methods for the same action. For example, one method will returns the object requested if available, otherwise null, while another method will return the object requested if available, otherwise it will throw an exception. The two methods have different names.

An example of this is the java Queue that gives you two options to remove an element from the queue: remove(), which throws an exception if the object is not found, and poll(), which returns null if it doesn't locate what you want it to remove. Both work the exact same way when successful, but have different ways of dealing with missing items.

This is what you have to do with your heap. You will have to provide two methods to remove the to top element (largest) of the heap: getTop() which will return null if the heap is empty, and pop() which will throw an exception of type HeapEmptyException if the heap is empty.

Moodle Submission

• You need to submit only one file: Heap.java
• This file should NOT contain the HeapEmptyException class.
• The moodle module contains a test program, and a copy of HeapEmptyException.
• The contents of the test program is not available. You have to test your program on your own thoroughly, so that you can be fairly sure that your program will work in most unknown conditions that require a heap. So your program must be robust to possible misuse that other programs may inflict on it. My test program will try different operations and report on whether your program passes the various tests.
  Please, do not ask for the code of the test program, it won't be released!
  Instead work on making your code simple, efficient, and robust.