# Lab 12: Heapsort

## Objective

To gain experience working with heaps and explore the heap sort algorithm.

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:

1. For each data item:
1. Add it to a heap.
2. Set i to 0
3. While the heap isn't empty:
1. Dequeue an item
2. Put that item in array[i]
3. 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

1. 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.
2. 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).
3. 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.
4. 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.
5. Next see how long the program takes to run on sizes 1,000 through 1,000,000 as you did for Lab 10. Compare the times taken to those you found in lab 10. Where does heap sort fall compared to bubble sort and merge sort?
6. 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:

1. How does heapsort compare to bubble sort and merge sort?
2. What is the Big-O of heapsort?

Submit the code on Canvas, and the answers as a comment on the submission please.