Assignment 7

The Assignment

Submission

• Email your assignment to ztomasze@hawaii.edu.
• Send me PriorityQueue.java (and Heap.java, if you write one, or any other classes needed to run your PriorityQueue).

Recommendations

Most of the code for the Heap is in your book. Read pages 519 through 532 to learn more about heaps and priority queues. There will likely be some differences--the book uses KeyedItems, where you will use Comparables. There may be other small differences. But the general algorithms for adding to and deleting from a Heap are there and should be a help. Remember, your heap should take Comparable objects; it shouldn't know anything about PrintJobs or other specific classes.

I recommend you write your heap as a separate class (Heap.java) and then use it in your PriorityQueue. (You may combine the two if you wish.) You must use a static data structure and the "(index * 2) + 1" formula. You may use an array, though I would recommend using a Vector. A Vector will grow as needed so you don't have to worry about the heap ever being full; and it has a toString() already written. (Of course, you could double the size of an array manually, and there are some methods in java.util.Arrays that will allow you to quickly print out an array. For example: java.util.Arrays.asList(yourArray).toString();.

Remember that the examples in the book assume that the object with the highest value key has the highest priority. Your heap should assume that the lowest value has the highest priority.

The two given queue exceptions do not compile under Java 1.3. Just comment out the two constructors that take Throwable objects. Also, you may comment out the package statement at the top of PriorityQueue if you are having trouble compiling.

Here is a short grader to check your PriorityQueue. You may have to run your own tests and do some debugging before you can pass this grader correctly. And remember this grader does not test exhaustively.

When you are done, try compiling and running Simulation with your PriorityQueue. It should throw no exceptions and print jobs in the correct order of fewest pages first.

Grading:

Out of 10 points:

1 - Compiles

2 - Documentation and Coding Standards

Most of the documentation of PriorityQueue is done for you already. Don't forget to add your name though. You may change any of the existing documentation (such as the class description) if you like. Document your Heap and its methods.

1 - Heap with a static data structure

At some point you should be using an array, Vector, ArrayList, or other static data structure to store your objects. And you should be storing your objects using the heap algorithm. That is, using the (index * 2) + 1 method of finding children, etc.

1 - size and empty methods.

1 - front method

Should show me (return) the highest priority (lowest value) item in the heap.

1.5 - enqueue

Adds items correctly without error. Note that it's hard to tell if you're adding elements correctly if there's no way to print out the heap/array. I highly recommend you have a toString or other method that shows what your heap looks like.

1.5 - dequeue

Successfully removes and returns the highest priority object from the queue.

1 - Works as part of the given Simulation code.

Don't change the method signatures of PriorityQueue and you'll probably be fine.

Solution

Zach's Solution (zip file).