Submission

Please zip your entire directory and submit it via moodle by Monday 4/9 at 11:59pm.

Goals

In this assignment, you will implement a BinaryHeap and use it to implement heap sort and a priority queue.

Part 1: Implementing a binary heap (45 points)

In this part, you will create a binary heap implementation that supports the max-heap property:

1. Define an interface Heap for the abstract data type (ADT) heap – what methods must this specify?
2. Define a class BinaryHeap that uses an array to implement your Heap interface.

Start with the starter code that can be found on moodle.

Hint: You may want to use the following snippet to deal with generics:

public interface Heap<T extends Comparable<T>>

and

public class BinaryHeap<T extends Comparable<T>> implements Heap <T> {

  // array to hold the heap

  private Comparable[] data;

  // keep track of the heap size (different from the capacity)

  private int heapSize;

}

Another hint: You may want to make an test your code with an array of Integers. Here is a method that will make an Integer[] from and int[].

public static Integer[] convertToIntegerArray( int[] a ) {

        Integer[] integerA = new Integer[a.length];

        for ( int i = 0; i < a.length; i++ ) {

            integerA[i] = new Integer(a[i]);

        }

        return integerA;

}

You can use it like this:

int[] ints = {2,1,3,10,15,8};

Integer[] array = convertToIntegerArray( ints );

Heap<Integer> myHeap = new BinaryHeap<Integer>( array );

Part 2: implementing heapsort (30 points)

Part 2a: heapsort algorithm (20 points)

Complete the static method heapSort in the ArraySorter class (part of the starter code) using your BinaryHeap.

Part 2b: JUnit Tests (10 points)

Create JUnit tests that check your BinaryHeap class.. The included base tests are simply to help you get your headers correctly formed so that they will match ours.

We will be testing your code using an expanded version of this provided tester, so please make sure not to change the headers!

Remember, your goal is 100% coverage, but your code must also achieve correct functionality.

Part 2c (bonus): GUI

Update the GUI from the included code to include heapSort.

Part 3: implementing a priority queue (20 points)

In this section, you will create a priority queue implementation. Base code has been provided below that will help you get started.

1. Define an interface PriorityQueue for the abstract data type priority queue. PriorityQueue represents a set of elements with keys whose values indicate a priority. At a minimum it should support the following operations:
   • insert( T element ) inserts a new element
   • maximum() returns max element (like peek)
   • extractMaximum() removes and returns max element
   • increaseValue(int index, T element) - sets the element at specified index to new elements. Fixes heap (through swaps) to move element to the correct position. You may assume that the value of the new element is greater than or equal to the value of the original element.
   • Refer to CLRS 6.5 for details.
2. Define a class PriorityQueueBH that uses your binary heap implementation from Part 1 to implement your PriorityQueue interface. PriorityQueueBH should have a constructor that takes a capacity as its only argument and creates an empty queue with the specified capacity. (You may create other constructors and methods if you wish.)

There is some stubbed out code and an example junit testing class in hw4.zip to help you understand method headers and basic behavior. Be sure to test further. You will be graded on your performance on our unit tests that expand upon the ones provided to you.

Submission

Include a README.txt file that clearly states:

• Your name and the name of the assignment
• Attribution for any sources
• Descriptions of each file