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.

  1. Checkout the BinaryHeaps project from your individual repository.
  2. 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.)
  3. 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().
  4. 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).
  5. 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.
  6. Before you write any method,
    1. Document the stubs.
    2. Then write the method itself.
    3. Then write a unit test.
    4. 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]". 
  7. 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.
  8. Tips for writing in-place heapsort!
    1. 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.
    2. 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!
    3. 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!
    4. Here is some sample code that implements these tips.
  9. Note: this code will become part of the SortingRaces assignment which will compare the speed of various sorting algorithms.