CS 206 - Introduction to Data Structures

Heaps

Due April 23 before 11:59:59 pm

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 my binary heap code from /home/gtowell/Public/206/a08/BinaryHeap.java. You will also need to get PriorityQInterface.java and AbstractPriorityQueue.java
  2. (20% of grade.) BinaryHeap.java is almost total undocumented. Add good, javadoc style documentation for this class. ("Javadoc" is the commenting stype you have been using all semester.) In addition to top level documentation of each method, add in-line comments that explain who the method works. (These in-line comments would certainly violate encapsulation.)
  3. (40% of grade) Create a new class TernaryHeap that extends BinaryHeap. Modify this class to be a ternary heap rather than a binary heap. You should NOT write any new methods. You will need to revise at least two of the methods in BinaryHeap. Do this my overriding the methods in BinaryHeap. 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 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. (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".

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/cs206/

  1. For this assignment N=7
  2. Put the README file into the project directory
  3. Go to the directory /home/YOU/cs206
  4. Enter /home/gtowell/bin/submit -c 206 -p N -d AssignmentN

For more on using the submit script click here