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. We are only giving you a single unit test just to demonstrate the interface.

  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. Write a unit test for it. The easiest way I found to create additional unit tests is just to copy the given unit test and rename it.
    3. Then write the method itself.
    4. Then you can add more tests untill you are confident it is correct. I will test it using my own tests, so it is in your interest to test your code thoroughly.
  6. For toString(), note that you can just call the built-in Array or ArrayList toString() method.
  7. 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.
  8. Note: this code will become part of the next assignment which will compare the speed of various sorting algorithms.