Your assignment is to implement eager-merge binomial heaps as described in class. You are provided with three files:
BinomHeapTest.java: This file contains the main class BinomHeapTest that is loaded when the interpreter starts up. It calls your binomial heap code.
EmptyHeapException.java: This file contains the definition of an exception that you will throw if a caller tries to find or delete the minimum element of an empty heap.
BinomHeap.java: This is the file you will modify. This file contains two classes: BinomTree, a (private) class whose instances are nodes of a binomial tree; and BinomHeap, a public class containing a number of public and private methods that implement eager-merge binomial heaps. The public methods are:
You must supply the missing code that implements eager-merge binomial heaps as described in class. The code should be implemented in a way that gives the amortized times as described in class. The only file that you should need to change is BinomHeap.java, and maybe also BinomHeapTest.java if you want to test out your code. We will be doing the same thing with a more extensive version of BinomHeapTest.java.
We have supplied the link procedure in the BinomTree class for linking two binomial trees of equal rank in such a way as to maintain heap order. If you wish to link trees t1 and t2 of rank i, just call t1.link(t2) and the new tree of rank i+1 is returned. The order of the trees doesn't matter; that is, calling t1.link(t2) has the same effect as calling t2.link(t1).
Instead of using a linked list of binomial trees as described in CLR, your BinomHeap should use an array as described in class. If h is a BinomHeap, then h.heap is an array of binomial trees. Each binomial tree is an instance of the class BinomTree. There is at most one tree of each rank i (recall rank = number of children). If there is a tree of rank i, then it is found at location i in the array h.heap. If there is no tree of rank i in h, then h.heap[i] is null. The value of h.largestRank gives the rank of the tree of greatest rank in the heap.
The children of any node in a binomial tree should be arranged in a singly linked list in order of strictly decreasing rank. However, you don't have to worry about sorting the list by rank, since the list will always be sorted naturally because of the way the linking is done.
All of the routines except merge and deleteMin are very easy. A user must create a new heap by calling the public method makeHeap. The user cannot call the constructor BinomHeap directly, since the constructor is private and cannot be accessed from outside the BinomHeap package. Note the package declarations at the top of each file; since the test program is in a different package, it cannot access the private methods of the BinomHeap package. The interface to your code is exclusively through the public methods.
To implement deleteMin, you should find the tree t containing the minimum data element (this should always be pointed to by min), create a new heap h1 from its children by calling the constructor BinomHeap(BinomTree b) with the list of children of t, remove t from h, then merge h1 into h by calling h.merge(h1). Don't forget that you have to update min and maybe largestRank. Also don't forget to handle the case of an empty heap.
The most difficult by far is merge. A call of the form h1.merge(h2) should merge h2 and h1, modifying h1 to be the new heap. You should implement the binary-addition-with-carry technique. Make sure you handle the degenerate cases where one of the two heaps is empty or where the user tries to merge a heap with itself, i.e. h.merge(h). Don't forget to update min and largestRank.
Clean, concise, elegant code. Lots of comments. At every step, tell us what you are doing and why. We are particularly interested in seeing your treatment of the merge function, which will require considerable ingenuity. Get started early!
See the MS Developer Studio handout and Programming Assignment 1 for basic information on how to set up your project. Your program should be compiled as a console application as with Programming Assignment 1.
You should submit your project online in the CSUGLab; instructions below. We will be using a test program that will exercise all the functionality that we have asked you to implement, including error handling. In addition, we would like you to pass in a printout of your new version of BinomHeap.java in class as usual.
For electronic submission, we have created a personal handin directory \\goose\courses\cs410-fall99\proj2\<login-id>, where <login-id> is your CSUGLab login identifier. Please check as soon as possible that this directory exists and that you can save files there.
When you are ready to submit, copy all the files in your project directory to your handin directory. Please copy your entire project, including all executables, .class files, source files, and project (.vjp, .sln) files into your handin directory.
If you are working with a partner, you only need to submit once, and you may submit it in either partner's handin directory. Please make sure both your names and Cornell IDs are returned by the names function.
The deadline for electronic submission is Tuesday, October 5, 7pm. At that time the permissions on the handin directory will change and you will not be able to access it. You may modify or replace files in your handin directory before the deadline as often as you wish.
Please contact cs410@cs.cornell.edu if you encounter problems.