To gain experience working with heaps and explore the heap sort algorithm.
Task
Heaps provide a way of sorting data. We can add the data into a heap
and then take it back out again (which will be in order). This algorithm is
given below:
For each data item:
Add it to a heap.
Set i to 0
While the heap isn't empty:
Dequeue an item
Put that item in array[i]
Increment i
For this lab you will implement this algorithm, measure the efficiency of the program,
and provide the Big-O analysis for heapsort.
Details
Start by downloading HeapSort.java. This file contains the
IntHeap class for storing a heap of integers that we talked about this week. It also contains
a skeleton program for doing sorting. There is already code to generate a random array, call
the sort and print out the time taken.
Next, change the heap from a max heap to a min heap. This will involve changing a few
things in the insert and dequeue methods (basically flipping a few < and > signs around).
Add the heap sort algorithm discussed above into the program. Run the program a couple of
times to verify that it's sorting the data correctly, in ascending order.
Then remove the code that prints the array out before and after sorting. It will get in
the way of timing how long the program takes.
Next see how long the program takes to run on sizes 1,000 through 1,000,000 as you did
for Lab 7. Compare the times taken to those you found in lab 7.
Where does heap sort fall compared to bubble sort and merge sort?
Lastly, what is the Big-O for heapsort? (Remember that the time to insert and dequeue
is $O(log N)$.
Submitting
When you're done, submit the code for your heap sort, along with answers to the two questions:
How does heapsort compare to bubble sort and merge sort?
What is the Big-O of heapsort?
Submit the code on Canvas, and the answers as a comment on the submission please.
