Project 4: d-ary Heaps

Due: Monday, 29 Aug 2011, at 23:59:59 PST

GRADING

You can see the file with which we tested your heap; it's here. To test your heap, first compile the tester: javac -cp .:junit-4.8.2.jar HeapTester.java (with junit and HeapImpl12.java in the same directory). Then run it: java -cp .:junit-4.8.2.jar org.junit.runner.JUnitCore HeapTester.

If your code passes the testSuperEasy test case, then you get a minimum score of 3.

Here is my solution.

Overview

In P4 you will be implementing (in a class called HeapImpl12) a d-ary heap using a Java array as the underlying storage. In particular, you must implement the Heap12 interface (the Javadoc is here).

Your HeapImpl12 class must offer a public constructor that takes exactly one parameter, d, that specifies the maximum number of children that any one node in the heap may have. The heap that your class implements must be a complete d-ary tree. You should use an array as the underlying storage for the tree. Similarly to what was demonstrated during class for binary heaps, you must devise a scheme to "map" any node of the d-ary tree into an array index. As the user adds elements to the heap, it may be necessary to "resize" the array of nodes; you should employ a similar method as was shown during lecture for the ArrayList implementation; this resizing should be hidden from the user completely.

You are encouraged to employ unit testing to test your heap implementation, but it is not strictly required for this assignment.

Your assignment will be graded using automated testers and also through manual inspection.

Help with generics

Your heap will store data of a generic type T. In contrast to the previous assignments, T cannot be just "any old Object" -- since a heap relies on the order relation defined among elements, the heap will require that the type T implement the Comparable interface. Any particular, T must satisfy the constraint that T extends Comparable<? super T>. This will be explained during class. When defining your class HeapImpl12, you should use the following syntax to ensure it compiles correctly:
public class HeapImpl12<T extends Comparable<? super T>> implements Heap12<T> { ...

To instantiate the array of nodes, you will need to downcast into the type T[] in a similar manner as you did in P3. However, for P4 you cannot just instantiate an Object[] array because the heap requires that the data all be Comparable; hence, instead you should instantiate the underlying array as: T[] nodeArray = (T[]) new Comparable[128]. (The choice of 128 was arbitrary.)

Grading

The maximum score on P4 is 8 points.

Submission

Submit your work using the bundleP4 script in the directory containing your HeapImpl12.java file. Make sure you are logged on to ieng6.ucsd.edu using your CSE 12-specific account. As always, make sure to submit before the deadline -- the script will show you (or anyone else) no mercy!