Lab 10b: Heaps and priority queues (revisited)

This lab is an opportunity to complete Lab 10 from last week, plus a chance to work more with scaffolding, assertions, and method overriding.

1. Starting out

Work with a partner, using the repository holding your work from last week. Before you do any work today, be sure that you have all of your work committed to Mercurial. To identify where you are starting, create a tag on your current revision with

hg tag Day2-start

After you do that, if you will be able to refer to this revision as Day2-start. You'll see that tag if you do hg log, and you can list the tags with hg tags. (The latter command will always show a revision with the tag tip.)

2. Using scaffolding

The methods you must write should work without relying on the scaffolding methods that I provided you. For example, checkHeap() should be used only for testing (and possibly in assertions).

If, for testing, you insert some additional printing of state, you should probably comment out those statements rather than deleting them. That could be helpful to whoever worked on your code in the future.

3. Using assertions

As demonstrated in class, you can add assert statements to your programs as a way to both document and check conditions that should be true. An assertion statement has the form

assert boolean-expression;

Add some useful assertions to your methods. It is often a good idea, for example, to assert the pre- and post-conditions of a method. If you have a nontrivial loop, you may want to assert its loop invariant.

The general rule is that the things that you include in assertions should not be extremely expensive to test. Using checkHeap() in an assertion might be pushing that boundary, but you should feel free to use it here as an exercise. (As noted in class, you may find it helpful to change checkHeap() to return true for empty subtrees (indices above heapSize.)

4. Overriding

Sometimes a method in a subclass needs to do what its parent's method does, plus a little more. We've seen examples of that in constructors, where we can call super() with suitable arguments to set things up.

You can use super a bit more flexibly than that: you can call any method in the parent class by explicitly calling it on the local name super.

Add a method toString() to your HeapSorter class. This method should return a string representation of the instance, showing the portion of the array that is already a heap followed by the elements that are not in the heap. Use the existing Heap.toString() method for the heap portion (which will be enclosed in braces), but add to that the remaining elements of the array in brackets. For example, you might get something like this:

heap { 55 44 33 22 11 } [ 66 77 88 99 ]

Add a statement inside the loop of sort() that prints out the state.

5. Bonus: Better display

If you have time, think about how you could print out a heap in a way that would show its tree structure. Write a method printAsTree() to class Heap that does this.

6. Handing in

Be sure that you have everything committed to your Mercurial repository. Then tag the final version in your repository as Day2-finish. Then, from your lab10 directory, turn it in with

/cslab/class/csci245/bin/handin lab10 .hg heap/*.java

Be sure that both partners have a copy of the code before you leave.