Lab 6: Heap Sort

Due Date and Submission Requirements

Due Date: Friday, March 7th at 11:59 p.m.
Partner Information: This is an individual assignment. You are allowed to collaborate with other students, but each student must submit their individual, independent solution.
Submission Instructions: Upload your solutions (.java file), entitled HeapSort.java to the BrightSpace(D2L) Lab 6 Dropbox.

The goal of this lab is:

Implement a Heap data structure to sort an array (Heap Sort)

Directions

Download Lab6Demo.Java as a starting point. You will write the HeapSort class (provided below), which will contain a method called heapSort(). This method must implement the Heap Sort algorithm that was discussed during lecture on 3/4. This method will return a sorted array. This class implements an interface, which makes your write the required methods for this lab. Given an unsorted array of integers, heap sort first constructs a Max Heap from the array. This will involve doing a for loop backwards through the array, and swapping the node with it's children if a child is larger than it.

Once the heap is created, the sorting can begin. The root node is swapped with the last element in the heap, and the new root is heapified down to its correct location. This process is repeated N times until the array is sorted (see lecture).

You must use a Max Heap like we did in class. Your heap sort algorithm must also be an in-place sorting algorithms, which means you must only modify the orginal array (you are not allowed to create a new array).

Your solution must include the following methods, and these methods must be used somewhere in your heap sort algorithm:

heapifyDown(int bound, int current)- This method will take an element in the heap (current) and move it down in the heap. This will likely be a recursive method, because the element might need to be moved down several levels in the heap.
buildHeap()- This method will take the unsorted array, and construct the max heap. You cannot create a new array. You must swap elements within this array to create the max heap.
swap(int i, int j)- This method swaps the elements located at index i and index j in the heap.

You will likely have more methods, but those methods are what's required.

Starting Code

Required Output

The output of your program should look exactly like this output. Your program should sort the integer array from least to greatest.

Grading (10 points)

HeapSort class is correctly defined - 1 points
heapifyDown() is used and is correct - 3 points
buildHeap() is used and is correct - 3 points
swap() method is used and is correct - 1 points
Array is correctly sorted from least to greatest. In-place sorting is done - 2 points

NOTE: If your code does not compile, correctness cannot be verified, and you won't receive any points for your code. Turn in code that compiles!