CS 151 - Introduction to Data Structures

Heaps

In class we have discussed heaps, specifically, binary heaps. In this assignment, you will create a ternary heap; that is a heap in which each parent has 3 children. Other than this change, a ternary heap is identical to a binary heap.

  1. Get the following code: These are all also available via cp or scp
  2. (20% of grade.) BinaryHeap.java is almost totally undocumented. Add good, javadoc style documentation for this class. ("Javadoc" is the commenting style you have been using all semester.) In addition to top level documentation of each method, add in-line comments that explain, in detail, how the removeTop method works.
  3. (40% of grade) Create a new class TernaryHeap that extends BinaryHeap. A Ternary Heap is identical to a Binary Heap except that each node has three children rather than two. In your TernaryHeap class you will need to override at least two methods of BinaryHeap, but you should not need any new methods. Suggestion, start by simply copying the methods you want to override. Then edit the copies within your TernaryHeap class. The top level comments you wrote for BinaryHeap should work without editing for TernaryHeap, so copy them over. Other than the testing code (see next) if you add more than 10 new lines of code to TernaryHeap you are doing something wrong.
  4. (30% of grade) The main function in BinaryHeap provides some minimal tests of a BinaryHeap based priority queue. The tests are very far from complete. Write a better set of tests for your ternary heap. For instance, you tests should test the behavior of the code when the heap is full and when the heap is empty. (A perfect set of tests will literally test the behavior of every statement in your code in a way such that you can verify that each line (or group of lines) behaves exactly correctly.) I do not expect perfect testing ... writing perfect tests often takes a lot longer than writing the code being tested ... I do expect tests better than "Jane Was Wet". (If your ternary heap implementation does not work, you may write these tests on the binary heap instead.) You can certainly write these tests before even starting work on the ternary heap.
  5. (5% of grade)Collect your testing output into a file. If you have not done so in your code, edit this file to explain the purpose of each test and what the output shows.

Electronic Submissions

Your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The submission should include the following items:

The following steps for submission assume that you created a project named AssignmentN in the directory /home/YOU/cs151/

  1. For this assignment N=7
  2. Put the README file into the project directory
  3. Put your annotated testing output into the project directory.
  4. Go to the directory /home/YOU/cs151
  5. Enter /home/gtowell/bin/submit -c 151 -p N -d AssignmentN