CSSE 230
BinaryHeaps
Overview
What? To implement insertion and deletion from a binary
min-heap, as well as heapsort.
Why? So that you will better understand the mechanics of the
binary heap algorithms.
Unlike previous assignments, we are giving you very little
code to start with. You will need to write, document, and unit test a
BinaryHeap class from scratch.
Pulling double duty: In this assignment, your BinaryHeap
class will be serving two distinct purposes: (a) as a data structure, namely
a binary heap, and (b) as a static-like class that heapsorts any array passed
as a parameter. Since the latter purpose requires use of a heap, and will
reuse some of the code from (a), it makes sense to put the code all
together, but the fact that the code is dual-purpose does cause some
interesting complications, noted below.
- Checkout the BinaryHeaps project from
your individual repository.
- While the heap must hold various types of data (like
Strings or Integers), the data types must at least be Comparable. So
declare your class like this:
public class BinaryHeap<T extends
Comparable<? super T>> { ... }
This is more complicated than the standard public class BinaryHeap<T extends
Comparable<?T> { ... }
,
but you'll sometimes see this, since it is more general, using a
wildcard to allow the compareTo() method to be defined at a superclass
of T (or, of course, in the T class itself.)
- How to store the data internally? We would like you to implement
in-place heapsort. Since the sort method is given a primitive array, that's the
data structure we have to use!
Thus, our BinaryHeap should be based on
a primitive array (which we can temporarily switch over to the passed array when
performing a sort() step.)
For your array initialization, you will need to
use the same workaround we used in the GrowableCircularQueue part of the
Stacks and Queues assignment: that is, your heap constructor will have to
take the type of T as input, and you should initialize your array using
Arrays.newInstance().
- If you let Eclipse stub in the methods in the unit tests,
it probably won't get all the parameter types correct. Fix the stubs to
be public void insert(T element), public
T deleteMin(), toString(), and public
void sort(T[] array).
- So far in this course, we've given you lots of unit tests
since writing good tests takes LOTS of time. (Consider EditorTrees!)
But after this course, you'll likely be writing your own tests. This is
a good chance to practice. We gave you a couple to get started. But you
should write more.
- Before you write any method,
- Document the stubs.
- Then write the method itself.
- Then write a unit test.
- Repeat (b) and (c) as needed to handle
increasingly-complicated test cases.
For toString(), note that you can just call the
built-in Arrays.toString() method. Unit tests will assume
the first element is null. For example, an array with just the element
of 17 yield the String, "[null, 17]".
- sort() will mutate the array passed to
it so that it its elements are sorted in increasing order. You are
required to write a (private) buildHeap helper method.
- Tips for writing in-place heapsort!
-
The sort() method is acting in a "static" way: it's supposed to sort the
passed array rather than the internal array field; however, all of your heap
methods operate on the internal field. To get them to operate on the
passed array, temporarily set your field to be the passed array. To be careful
(in case the BinaryHeap object is being used as a data structure) you might
want to save the existing field to a temporary variable before doing this,
and after the sorting is done, set the field back to its original value.
- What to do about the 0th entry, which the heap methods assume
is unused/null, but in the passed array is a real element to sort? There
are several ways you could accommodate this. One cumbersome way would
be to change all of your index calculations so that the 0th entry is not wasted.
However, here is an easy and clever alternative: before running heapsort,
run a "single step of selection sort": use an O(N) loop to find the smallest
element in the array, then swap it into the 0th location. Now, you can run
heapsort on rest of the array, ignoring the 0th location, because the correct
element is there already!
- In-place heapsort requires a max-heap; how do I modify my min-heap
class without rewriting all the code? Add a Comparator field to the
BinaryHeap class, where the default constructor
initializes a natural (ascending) Comparator (that you define). Use the
comparator (rather than compareTo) in your percolation methods.
Then, if you want to sort, change the
Comparator to a reverse (descending) Comparator - voila, your min-heap
code now creates a max-heap!
-
Here is some sample code that implements these tips.
- Note: this code will become part of the SortingRaces assignment
which will compare the speed of various sorting algorithms.