CS 14 Binomial Heap

Due Thursday, August 26th @ 8pm

CS 14 Homepage
Your assignment is to implement a Binomial Heap. A Binomial Heap is a data structure that has similar behavior to a heap, but also allows (in O(log n) time) the merge operation: given two heaps, merge the contents of one Binomial Heap into another. Binomial Heaps combine many of the best things about heaps with a healthy dose of linked-lists. In order to implement a Binomial Heap, there is only 1 function of any great complexity that you must implement. I will describe here the functions that you will need, and provide you the interface I will be testing with. Your job is not only to implement that interface, but to also make sure the output from your << operator is identical to mine (this way I can quickly check your heap structure.) You will need to write a simple testing interface in main(), and should perform sufficient tests to ensure you have gotten everything working properly. Sample inputs and outputs are provided at the bottom of this page.

Binomial Heaps

To understand Binomial Heaps, you must understand Binomial Trees. The idea of a Binomial Tree is this: Binomial Trees are NOT binary. They may have an arbitrary number of children. (For the purposes of our implementation, rather than having a vector of pointers to our children, we will deal with this as a pointer to the left-most child, which has a pointer to its sibling to the right, which has a pointer to the sibling to its right, etc). The 0th Binomial Tree is the singleton tree (a tree with a single value). The K+1th Binomial Tree is a copy of the Kth Binomial Tree with a second copy of the Kth Binomial Tree as the leftmost child of the root. Like this:

Notice that the second tree is just 2 copies of the first, with the child pointer of the root copy pointing to the root of the second copy. Notice that the third tree is just 2 copies of the second, with the child pointer of the root copy pointing to the root of the third copy. And so on and so on.

A Binomial Heap is a collection of binomial trees, each of which satisfies the regular heap property (in this case, we are doing min-heaps.) Everything that is a child (everything in the linked-list beginning with the child) must have a LARGER value than the value stored in any given node. Additionally, no two trees in the collection may be the same size (which is equivalent to not having the same degree at the root).

Now we have a list of n-ary heaps (remember, we keep a root, which has a sibling which is also a root, etc). Finding the minimum value in our Binomial Heap is easy: it must be the minimum of the root values of our heaps. This is nothing more than iterating through a linked list.

The Insert, Remove, and Merge operations all can be implemented using a single complex operation: HeapMerge. Given two heaps, iterate through the root-lists of both heaps, and join them together into a single list such that the degree (number of children of the root) is in sorted (smallest to largest) order. This step is relatively easy. The harder step (in fact, the only truly difficult part of this entire data structure) is ensuring that no two roots may have the same degree. If they do, you must merge them together into the next-larger binomial heap. (This is easy, just decide which has a smaller root value and make the other its child.)

There is a strong possibility that you will have a "carry": if you originally had heaps of degree 1, 1, and 2, then merging the 1's gives you a second heap of degree 2, which must be merged into a heap of degree 3. This can go on for quite a while (the entire length of the merged list, actually), so be careful.

The two phases of HeapMerge are each about 50 lines of C++ code, and heavy on pointers. It is highly recommended that you draw the pointer operations for this before you start implementing it. If you can implement this function, the rest of the assignment is fairly easy. Without this function, the assignment is essentially impossible.

Given HeapMerge, Insert is easy: create a new tree of size 1. This is a valid Binomial Heap. Now call HeapMerge on the existing root list and the new node.

Given HeapMerge, Merge is easy: call HeapMerge on the root lists of the two heaps.

Given HeapMerge, ExtractMin is fairly easy. First, find the root in the root list containing the minimum value. Remove it from the root list, but don't delete it yet. Write a recursive function Node* reverseList(Node* list, Node* ret) which will return you the reverse of list followed by ret. (HINT: the base case is to return ret when list is empty, and the function should be less than 5 lines of code.) Given the structure of a binomial heap, you are now guaranteed that the children list will be in order (smallest degree to largest degree), so you call HeapMerge. Then delete the min, and return the value held in it.

Size is best stored, not calculated.

Details

You must implement the interface defined in binheap.h, and make sure that all of the behaviors of the program are implemented correctly. You may ADD to this interface, but you may not alter any functions. We will be testing your submission by compiling your submission file with our main function and testing in our main function.

Phase I

Since this is a more conceptually challenging structure than many that we've covered, 15% of your grade will be based on your ability to explain your program to me during office hours on Monday, August 23rd. You must be able to clearly and concisely explain what the structure looks like, or at the very least draw out what the operations will do. I will happily fix any misunderstandings that you have at that point, but it will cost you some of that 15%.

Tests

Here are 3 sample tests. Keep in mind that these tests do not cover a full (arbitrary size) Merge (operator +=) operation. You must test that on your own.

test1.input test1.output
test2.input test2.output
test3.input test3.output

Hints