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>> { ... }
  3. Choose how to store the data internally. Weiss uses arrays, but ArrayLists also have advantages. 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. Before you write any method,
    1. Document the stubs
    2. Then write the method itself.
    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]". 
  6. sort() will mutate the array passed to it so that it its elements are sorted in increasing order. Note that you will want 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.
  7. Note: this code will become part of the next assignment which will compare the speed of various sorting algorithms.