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. 

  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 type T to be compared to any other type that has type T as a superclass.
  3. Choose how to store the data internally. Weiss uses arrays, but ArrayLists also have advantages. I find ArrayLists easier if you don't care about doing heapsort in place. See the note under sort() before you decide.
  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 Array or ArrayList 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.
    1. Hint: you are not required to do the sort in-place, but may use the less efficient version that copies from the array to the min-heap’s array or ArrayList and back. Indeed, the in-place version requires a max-heap. However, here's a suggestion of a nifty way to make a max heap. Have a Comparator field, where the default constructor initializes a default (ascending) Comparator. Use the comparator 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. Then, if you do use an array instead of an ArrayList, you can sort in-place if you want to.
  8. Note: this code will become part of the next assignment which will compare the speed of various sorting algorithms.