Fish Food
a.k.a.
Heap!
Due: March 11, 11:59 pm
Read this whole handout! Yes, this is important. While you are at it, do all the readings associated with the assignment. This is especially important for this assignment in particular! If you understand what Priority Queues and Heaps are before you start, you will be much better off.
In this assignment you will implement a priority queue using a heap as the underlying data structure. Your heap implementation will be based on a version of a link-based binary tree which you will modify. When your program is fully functional, a visualization tool can use your completed data structure as the basis for a shortest-path algorithm that you'll be learning about later in this class. For now, don't worry about how that works and just watch the pretty flagella float around!
In addition to the ordinary heap operations, you must implement the getTree() method in your MyHeap class so that the visualizer can work. The getTree() method is similar to the getData() method in the Queue assignment: it breaks encapsulation by allowing the binary tree underlying your heap to be publicly exposed (generally a bad thing), but allows you to see graphically how the heap is storing information. You must also implement the size() method, as the sizing of the visualizer window depends on it.
Type 'cs016_install heap' to install the project.
Type 'make' in the heap directory to compile your code.
Type 'make run' in the heap directory to run your code.
Type 'cs016_handin heap' to hand in your code.
Type 'cs016_runDemo heap' to run the demo.
Priority Queues
Priority Queues provides ADTs for priority queues and comparators, and explains the use of priority queues in sorting algorithms.
Heaps
Heap gives an explanation of heaps, as well as describing insertion and removal and explaining how to update the heap to maintain heap order after these processes.
Introduction to Heaps gives some more specifics about the implementation of upheap and downheap.
Binary Search Trees is a nifty little Java applet that goes step-by-step through inserting, deleting, and searching for items in a variety of different types of trees.
Adaptable Priority Queues
Adaptable PQs gives an explanation of adaptable priority queues which, in addition to the general priority queue ADT methods, include the methods:
replaceKey(e,k) which replaces the key of entry e with key k,
replaceValue(e,x) which replaces the value of entry e with x, and
remove(e) which removes entry e from the queue.
The purpose of this assignment is to help you ...
The next three paragraphs provide a general idea about how the visualizer works. The best way to learn how to use the program is to play with the demo.
The top portion of the visualizer is where you will be able to see your tree, with circles representing the internal nodes. Nodes connect to each other with single black lines. As your tree grows in size, the scrollable window will shift to accommodate the extra branches.
The buttons are self-explanatory if you have looked at the methods your heap must implement. The size() button will print out the size of the heap and isEmpty() will tell you whether the heap is empty. removeMin() removes the element at the top of the heap, while min() indicates which element is the minimum by changing its color to pink.
If a button has a variable in parentheses, it will need the parameter specified. For example, insert(key,val) takes its key and value from randomized text boxes in the third row, while remove(entry) needs a target entry to eliminate from the tree. You can provide the entry to remove by clicking an internal node with your mouse. The selected node turns pink, while all unselected internal nodes remain blue. If you wish, you may uncheck the “Random” boxes and specify a key or value before using the replace methods. Finally, clicking the “Make Invalid Item” button generates an invalid key/value pair which should trigger your InvalidKeyException. The text area at the bottom of the window will indicate whether this has happened successfully. There is no way to trigger an InvalidEntryException using the visualizer (sorry!), so you'll simply have to think that through carefully. Leaving "INV" in the value box does not constitute an invalid Entry.
You will be constructing your heap on top of a link-based binary tree. You should design the program before you start coding, as starting over at the last minute because you did not put enough thought into design isn't fun. Feel free to come to TA hours if you have questions about your design. Attending the information session is one of the best ways to ensure you get started on the right track. The following are some key points you should be considering:
For this assignment, we're asking you to also hand in a README documenting your design. Please answer the following questions in a simple text file entitled "README" placed in the same directory as your project. When you use the handin script, the file will be packaged along with your code. Each of the questions should be answered in about 2-4 lines. Only exceed this limit if you feel your design warrants more detail; remember that additional commenting may be better appreciated than a long README if you feel you have a lot to say!
In Queue, we included in the program handout additional information on the interfaces and inheritance structure of the support code. Oh, you didn't know how good you had it back then. This time, we're going to make you work just a little harder for that information.
Instead of including running time information and method signatures here, we're asking that you examine the Javadocs for "Heap" linked off the CS16 homepage (on the left sidebar listed as "Support"). These documents contain all the information you'll ever need, so if you haven't used Javadocs before, now is a great time to learn. They're highly self-explanatory and are quite useful in "linking together" information such as the classes that implement certain interfaces, what parameters need to be passed to methods, the return type and exception-throwing signature of a method, etc. The documentation is automatically generated from comments in the stencil code, so you'll have a ready reference in the Java files while you're doing the actual coding.
We're expecting you to concentrate on the classes in the heap package (rather than the support.heap package) while browsing the Javadocs, as this is where the essential information is. The rest of it is simply the classes we use to launch the visualizer, so it won't help you much to go through the support.heap documentation. You can if you're really curious, but don't say we didn't warn you. If you're new to Javadocs, feel free to drop by TA hours and we'll go over how they work.
Remember: The most important information contained in the Javadocs is the running time each method must observe. Running time adherence is a significant portion of your program grade, so don't gloss over this!
There are a few exceptions you'll need to throw for Heap, and each is well-defined in the program stencil code. Every method that requires an exception is specified in the stencil code, so you do not need to come up with any other times when these exceptions should be thrown. You can find all the information presented here in the Javadocs as well, but we thought we'd put it here as well for reference purposes.
Those are the nuts and bolts of heap! Remember to read the references before even thinking about starting to code. There are quite a few resources available for this project – the textbook, lecture slides, Javadocs, and your friendly TA staff – so use them! You may be sick of hearing this from CS15, but please do start early. Heap is nestled in there between a couple homeworks and the midterm exam, so while you may think you have lots of time, it'll creep up on you fast if you put it off while doing other work. Good luck!