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.
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.
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.
7. Note: this code will become part of the next assignment which will compare the speed of various sorting algorithms.