CS 201: Data Structures (Winter 2018)
HW10: Heap builder
Due: Wednesday, 02/28 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.)
- For a heap with n items and 2 children each, how many levels are in the heap?
- For a heap with n items and k children each, how many levels are in the heap?
- 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 azip
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.