CS 201: Data Structures (Spring 2018)

HW10: Heap builder

Due: Monday, 05/21 at 22:00

1. Goals

To understand array-based heaps (and take another break from larger projects).

2. Setup

This is a solo programming assignment. You can share ideas and thoughts with other people in the class, but the code that you submit should be your own. You are also welcome to talk to me, the prefect, or the CS lab assistants for help.

Download MaxHeap.java.

3. Coding portion

MaxHeap.java implements a maxheap and runs some tests on it. This is essentially code that I took completely from the textbook, but simplified a little.

Write a class, called BigFamilyMaxHeap, by modifying MaxHeap so that instead of just being a binary heap (i.e., every node has two children), your class can allow each node to have k children, where k is a parameter that you supply to the constructor. (We'll assume k is an integer greater than or equal to 2). Note that the MaxHeap class I supply already has such a parameter, but I ignore it.

This approach of having more children than 2 is less efficient than using two children. Don't walk away thinking that this is actually a good idea. But it's a neat exercise that has some interesting lessons in it.

4. Code notes

Accomplish your goal by changing as few lines as possible in the code that I supply. We will grade you, in part, on how optimal you can be about changing as few lines as you can to make this work. We're not going to go crazy about making small distinctions, but the idea is to encourage you to solve the problem by modifying this program, as opposed to developing your own instead.

One convenient way to measure differences in files is to use the command diff. For example, if I have two files, I can display the differences between them to the screen via the command:

diff file1.txt file2.txt

You'll actually be interested in counting the number of lines. One can work really carefully at this, but we're just going to run this command:

diff MaxHeap.java BigFamilyMaxHeap.java | wc -l

which counts the number of lines in the entire diff output. Technically, this is double counting: it counts the number of lines in MaxHeap.java that's different from BigFamilyMaxHeap.java and vice-versa. It also counts some lines with some administrative gunk that diff spits out. But it's an easy way for us to get a rough sense of how much of the original program you have changed.

Do not change any of the code in main, as we will use this to test your code.

5. Written portion

Answer the following questions and submit it along with your code.

(Submit a plain text or PDF document. As before, you may convert other documents formats to PDF, or scan hand-written answers.)

1. For a heap with n items and 2 children each, how many levels are in the heap?
2. For a heap with n items and k children each, how many levels are in the heap?
3. You should find that the number of levels for a heap with k children is less than or equal to the number of levels for a heap with 2 children (if k > 2). It seems as though one should then conclude that we should make k as high as possible. A shorter tree should result in fewer comparisons, since we are navigating fewer levels. Or are we? Where's the flaw in this thinking?

6. Submission and grading

Submit to Moodle a zip archive containing:

• BigFamilyMaxHeap.java and
• written analysis, in .txt or .pdf format.

Assignment requirements

This is a partial list of the things that we'll be looking for when evaluating your work:

• Correct implementation of an array-based maxheap where each node can have k children.
• Heavy reuse of the supplied starter code by modifying only a few lines.
• Correct written analysis.

Grading

• Coding portion [10 points]
• Written portion [5 points]

Start early, have fun, and discuss questions on Moodle.