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.

• Introduction

  • 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!

• Java Classes and the Visualizer

  • 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.

• Installing/Compiling/Handing In/Demo

  • 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.
    
    
    

Reading

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.

• Specifications
  • Purpose

    • The purpose of this assignment is to help you ...

    • understand a link-based binary tree and its use within a heap
    • identify the advantages of the interface provided by a complete binary tree
    • gain experience in implementing and using a heap and a priority queue
    • extend your understanding of Positions and how they differ from Entries
    • learn about using comparators and become comfortable throwing exceptions
  • Requirements
    • You will write MyLinkedHeapTree<E>, an implementation of the interface CompleteBinaryTree<E> from the net.datastructures 4.0 package (hereafter referred to as “NDS4”). This class will serve as the modified link-based binary tree on top of which your heap will be constructed. Note that much of the binary tree functionality of this class is inherited from the NDS4 class LinkedBinaryTree<E>. You will want to read the Javadocs of this class carefully to understand how the class you are extending operates. Remember that the generic E represents the type of the elements the tree is capable of holding.
    • You will write MyHeap<K,V>, an implementation of the interface AdaptablePriorityQueue<K,V> from the NDS4 package. This class represents the heap itself, relying on an underlying complete binary tree (your MyLinkedHeapTree<E>) to hold its data. Remember that the generics K and V represent the types of the key/value pair for every element in the heap. Be certain you understand the distinction between a normal priority queue and an adaptable one: an adaptable priority queue has several features not available in a normal priority queue, such as the ability to replace keys and values after they've been added and the option of removing an item not lying at the top of the heap.
    • Finally, you will write a MyHeapEntry<K,V> class, an implementation of Entry<K,V>, to store a key/value pair. While classes to hold key/value pairs are available within NDS4, your implementation will require several additional accessors and mutators so that you can perform all the actions associated with an adaptable PQ. Think about the relationship between your Entry implementation and the Positions (or “nodes,” as you may think of them) which will hold each element in the binary tree. The adaptable priority queue reading may provide some insight into the additional methods you'll need for this class which aren't in the interface.
    • Throw the exceptions documented in the interfaces you are implementing. This will require interpreting the conditions that cause an exception and writing code to check whether those conditions exist.
    • A README file as described in this handout.
• Visualization

  • 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.

• Design

  • 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:

    • Positions vs. Entries – Before you begin thinking about how to implement your classes, you need to have a solid understanding of the distinction between Positions and Entries in the data structure. A Position is a tree node. It is a container for an Entry: once created, a Position stays in the same place in the tree until it is deleted. However, Entries can be moved among Positions freely. Notice that the NDS4 Position<E> interface contains a generic E, which is the type of the element a Position contains.
    • Entry Key/Value Pairs – So what elements do the Positions of your tree contain? They contain references to other positions (children, parent) and an Entry<K,V>. Entries contain a key/value pair (hence, K and V) and are the data-containing elements of your heap. For example, the Entries used in the visualizer consist of an integer key between 1 and 99 and a string value of three characters. Positions are tied down in a single location on the heap because it's too much work to re-link parent and child nodes every time you want to up-heap or down-heap. Instead, the Entries contained within the Positions move, swapping themselves between Positions when called for in heap-order restoration. It's a subtle distinction, so re-examine the adaptable priority queue reference and see a TA if you're still confused.
    • Extra MyHeapEntry Methods – You may have noticed that MyHeapEntry<K,V> is one of the classes we are asking you to write. This requires a bit more thinking than it first appears, as you cannot simply implement the accessor methods defined by the interface and be done with it. Think about the replace methods: replaceKey(...) and replaceValue(...). It doesn't make sense to simply instantiate a new Entry every time you need to alter the contents of an existing one. Perhaps some mutator or "set" methods would be helpful? More substantially, you need to think about the Entry's relationship with the Position holding it. Why does an Entry need to know its location in the Heap? What should happen when an entry's key is changed? See the description of "location-aware entry" in the adaptable priority queue web reference.
    • Complete Binary Trees – One of your major tasks in the assignment is adapting the LinkedBinaryTree<E> from NDS4 so that it represents a complete binary tree. Doing so means ensuring that the tree always knows where the "last" node is – the node to be eliminated in case of a remove() call – and where the next node to be inserted should go. This is far more complicated than it may first appear, as not only are the two nodes not necessarily close to each other, but the stringent running time requirements of the MyHeap<K,V> depend on the complete binary tree's add(...) and remove() methods being efficiently implemented. This means the methods you implement in MyLinkedHeapTree<E> must run in O(1) time! More on this in the next two bullets ...
    • "Node-Tracking" Algorithms – We're not explicitly telling you how to implement your "node-tracking" in MyLinkedHeapTree<E>, so you have several options. The in class slides on Heaps and Heap-Sort contain a rudimentary algorithm for finding the parent under which to insert new nodes given the current last node. This algorithm runs in time proportional to the height of the tree (i.e. O(log n)), but over a series of insertions and deletions, its amortized running time is in fact O(1); put plainly, this means that, yes, you can use it in your MyLinkedHeapTree<E>. The question now becomes, "how do I track the last node as I insert and remove elements?" A fundamental data structure may help you with this ... perhaps something in which you can "push" added nodes and "pop" removed nodes?
    • Alternative "Node-Tracking" – There are, in fact, more efficient (and more elegant) ways to keep track of your "last" node and your "insertion parent" node than the algorithm we've hinted at above. Think about what types of data structures might be useful here, and remember that your choice of implementation is completely up to you. All the classes of the net.datastructures package are at your disposal, and anything that will run the add(...) and remove() operations in O(1) time and with reasonable space usage is acceptable. Feel free to do a sanity check with a TA if you'd like to try a more ambitious method. Creativity will be rewarded! (Hint: the "Deque" variety of a standard queue may be helpful for one approach to solving the problem.)
    • Understanding MyHeap – This class will contain the majority of the code you write, but it doesn't have to be too difficult. In the requirements section, we warned you about the distinction between an adaptable priority queue (which you are implementing) and a normal priority queue (which the textbook goes into in depth, including code samples). We cannot emphasize enough that you should read the book chapters before coding this class! You won't be able to just copy code right out of the textbook – at least, not for every method – but it'll certainly get you started toward modifying the heap for adaptable methods!
• The README

  • 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!

    • Discuss the design choices you made in your MyHeapEntry<K,V> implementation and explain why you chose those additional methods.
    • Explain how you implemented a CompleteBinaryTree<E> using the LinkedBinaryTree<E> as a starting point. What was your method for finding where to add and remove nodes in the tree? Can you characterize the running time of MyLinkedHeapTree<E> methods?
    • How did you eliminate repeated blocks of code by using private or protected "helper" methods in your MyHeap<K,V>? Include anything else notable about your implementation.
    • As with all programs in CS16, the TA staff has automated testing utilities for Heap that help us assess the functionality of your program. If there is a bug in your code, we will find it, we promise. However, if you notice a bug that you just can't seem to fix (or don't have the time to fix), let us know in your README and you shall be rewarded! Just tell us what goes wrong, what functionality is affected, and roughly where you think the problem is, and we'll give you some points back. It won't be much, but you'll lose fewer than if you pretended it wasn't there and forced us to find it ourselves. It's easier on us and shows that you put some effort into testing rather than just being sloppy.
• Support Code
  • Interfaces and Javadocs

    • 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!

  • Exceptions

    • 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.

    • IllegalStateException – An exception from the java.lang package intended to be thrown when a method has been invoked at an illegal or inappropriate time. Here, we are using it to signal that a priority queue cannot change the comparator it is using unless it is currently empty. Thrown in MyHeap.setComparator(...) only, as you might expect.
    • EmptyPriorityQueueException – An exception from NDS4 indicating that the priority queue cannot fulfill the requested operation because it is empty. Thrown in MyHeap.min() and MyHeap.removeMin(), as you can't remove elements from an empty heap.
    • InvalidKeyException – An exception from NDS4 indicating that the key being handled has been determined to be invalid. The Comparator in use is the only object that can determine a key's validity, so you might want to examine the compare(...) method of that class for a way to distinguish valid from invalid keys. This exception may require that you use a try/catch block (unlike the previous two exceptions) so check out the slides labeled "A Necessary Digression to Necessary Java" if you don't feel comfortable with the syntax. MyHeap.insert(...) is the only method with a signature explicitly throwing this exception, but you may find it makes sense to throw it from MyHeap.replaceKey(...) as well.
    • InvalidEntryException – An exception from NDS4 thrown when the Entry<K,V> being handled is invalid. For example, an Entry that is actually null would be invalid, as would an Entry that is not of the type being used in your Heap (think about or research ways you might detect this). If you find yourself needing to cast MyHeapEntry<K,V> objects to access additional methods, a helper method in MyHeap<K,V> that first checks validity might be useful to have around. Thrown in MyHeap.remove(...), MyHeap.replaceKey(...), and MyHeap.replaceValue(...) if the Entry parameter isn't quite right.
    • EmptyTreeException – Similar to an EmptyPriorityQueueException in that it's an NDS4 exception indicating that the tree cannot fulfill the requested operation because it is empty. You should never see this thrown from your heap simply because the EmptyPriorityQueueException "intercepts" the same condition first, but you need to throw it from MyLinkedHeapTree.remove() to ensure your CompleteBinaryTree<E> implementation is usable in other contexts.
• Closing

  • 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!