In this task we will implement Heap Sorting.
Download the lab12 folder from the download directory.
You will complete the class HeapSort.java, located in the javafoundations package.
Because we want our algorithm to be able to sort any kind of objects, we will use generics. And since sorting involves comparing, the class header should look as follows:
public class HeapSort<T extends Comparable<T>>
Examine the starter code in HeapSort.java. Notice the instance variable, maxHeap, declared to be of type MaxHeap:
private MaxHeap<T> maxHeap; Since MaxHeap is an Interface, it cannot be instantiated. So, you will need to choose a specific implementation of the MaxHeap Interface to initialize that instance variable. We suggest you use the LinkedMaxHeap implementation of the MaxHeap Interface.
Define a method with the following header:
public Vector<T> sortInDescending(Vector<T> toSort)
As the name indicates, this method will take as input a vector toSort and will return another vector (named results), that contains the same items but in descending order. That is, the first element in the results vector is the largest element in the toSort vector, and the last element in the results vector is the smallest element in the toSort vector.
To do that you will use a heap. In particular, use a maxHeap. Your code should follow these steps:
Remove the maximum of the heap, and add it to the results vector.
Repeat step 2 above until there are no elements left on the heap.
At the end of this process, the results vector will contain all the input data in descending (decreasing) order.
Write a driver class to test the sorting method. Where should you save this class? Should it be part of the javafoundations package, or not?
Test it with a couple of different kinds of objects, such as Integers and Strings. Make sure you print your testing input before and after the sorting to see that it has been sorted correctly. What other data types can you sort?
What if you wanted to sort in increasing order? Define a method called sortInAscending that is using the MaxHeap you used before. You could, of course, implement this method using MinHeap, but for this lab do not use a MinHeap, use the sortInDescending method you wrote above!
public Vector<T> sortInAscending(Vector<T> toSort)
Test this method in the driver to make sure it works correctly.
In the lab12 folder you have the files that we used back at the lab of Shapes.
Create a vector of Shapes and add a few shapes (Circles, Rectangles, Squares) in it.
Then sort them.
How is this possible? Look at the way class Shape is defined: it implement Comparable<Shape>!