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, you will create a BinaryHeap class that will be serving two distinct purposes: (a) as a data structure, namely a binary heap, and (b) to support a static (heap)sort method that will sort 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.

Instructions

1. Get the starting code from your the following Github link.
2. The heap must hold various types of data (like Strings or Integers), so we need to declare this new class to be generic, parameterized by type T. The type T data type must at least be Comparable. So declare the BinaryHeap 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). See Weiss's discussion of 'type bounds' in Section 4.7.4 in the Fourth Edition.
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. 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. It is recommend that you navigate to the BinaryHeapTest.java file and use Eclipse for generating the stubs for all the BinaryHeap methods. Eclipse will probably not get all the parameter types correct for the methods that you ask it to generate, so after Eclipse generates these stubs, manually fix each one so that the method manipulates the generic type T instead of 'Object' (which is what Eclipse will guess as the data type). Here is a list:
   • public void insert(T element)
   • public T deleteMin()
   • public String toString()
   • public static<T extends Comparable<? super T>> void sort(T[] array, Class<T> type)
5. So far in this course, we've given you lots of unit tests so that you could focus on developing the data structures and algorithms (writing good tests takes LOTS of time, consider EditorTrees for example). In subsequent courses, you will be writing your own tests. This BinaryHeaps will be good chance to practice for starting to write your own unit tests. We have given you a few simple tests for BinaryHeaps to help you get started. But you should write more.

Before you write any method, Document the BinaryHeap stubs. Then implement the BinaryHeap methods. Then write a unit test - 1st test 'steady state', i.e., normal situations. Then think about and develop tests for edge cases. Repeat steps #2 and #3 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]".  sort() will mutate the array passed to it so that its elements are sorted in increasing order. You are required to write a (private) buildHeap helper method.

Tips for writing in-place heapsort!

• 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!
• The sort() method is static: how do I use generics in a static method? Try class declaration public static<T extends Comparable<? super T>> void sort(T[] array, Class<T> type) .
• The sort() method is given an array to sort; how do I turn that into a heap? Have the sort method initialize its own BinaryHeap, using a new constructor that you define: this constructor takes the array as an argument, and sets its heap to be that array; finally, it runs buildHeap() so that by the time the constructor is finished, you have a valid heap.
• 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 your BinaryHeap class, and use its .compare() method rather than T's .compareTo() method whenever you compare elements in the percolation methods. By default, you are creating a min-heap, and so the default constructor initializes a natural (ascending) Comparator (that you define, using compareTo()). If instead, you want a max-heap, set the Comparator to a reverse (descending) Comparator - voila, your min-heap code now creates a max-heap! You might want to add an extra boolean argument to the BinaryHeap constructor/s to tell it whether it's a min-heap or a max-heap; your constructor can then initialize the comparator appropriately.

Grading

You will not be submitting this assignment directly, and it doesn't have an independent due date.

Instead, BinaryHeaps will be graded as part of the later SortingRaces assignment which will compare the speed of various sorting algorithms, including your heapsort implementation. You will be copying your BinaryHeaps class into that project as a first step. (SortingRaces will also include tests that grade the correctness of the heap data structure implementation.)