# Homework 8: Implementing a heap

**Due before class on Monday, November 16**- Submit using the submit program
as
`312 hw 08`

.

# 1 Overview

Modern road races are "chip-timed", which means that competitors can start and finish at different times, and the winner is not necessarily the person who crosses the finish line first.

Your task for this homework will be to complete the implementation of a program that reads in a whole bunch of names and times, and prints out the names of the top K finishers with the lowest times, where the value of K is specified as a command-line argument. To do that, of course, you will be completing the implementation of a Heap.

# 2 Starter code

You can get all these files at once by downloading the file
hw08.tar.gz
and running `tar xzvf hw08.tar.gz`

# 3 Details

The `TopK.java`

program is already written for you.
It creates a max-heap, reads in all the names and times, calling
`removeMax`

as necessary to maintain the heap size of K,
and finally prints out the contents of the heap to show the top K
finishers.

You just need to fill in the `TimeHeap.java`

methods
for doing insertion and removal from the heap. There is an inner class
`Entry`

that contains a time and a name for you to insert
into an array-based heap. You can use an actual array of type
`Entry[]`

or an instance of `ArrayList<Entry>`

;
your choice.

# 4 BONUS opportunity

But wait, there is another way to do it! Instead of using a max-heap, whose size is always at most K+1, you could instead create one big min-heap with a "heapify" operation, then call removeMin K times to get the K smallest things. Instead of \(O(n \log K)\), this way would only have running time \(O(n + K\log n)\), which is potentially much better!

For this, you will create a min-heap instead of a max-heap. So your
`TimeHeap`

class will have a `removeMin`

operation
instead of `removeMax`

. Oh, and you will also have to write
a `heapify`

method, and adjust the `TopK.java`

program
as necessary to make the appropriate calls.

This is harder, so I provide an incentive: **If you do it this way
with a min-heap,
your lowest HW grade from the first 7 homeworks will be overwritten with
this HW grade**.

And, as usual, the fastest program in the class wins a tangible prize. Are you up to the challenge? I hope so. Good luck!

# 5 Example

When everything works, if your program is run with
`java TopK 10`

and then the following is typed
into standard in (followed by ctrl-D):

Nathan 609601 Liam 707303 Logan 318344 Ethan 91286 Jacob 334328 William 631989 Samuel 592643 Sofia 492706 Sara 964558 Isabella 878226 Ava 613357 Emma 366389 Noah 60429 Emily 474105 Benjamin 645060 Chloe 481035 Lucas 502159 Maya 248729 Olivia 109154 Leah 28141

then the output should be

10. Chloe 9. Emily 8. Emma 7. Jacob 6. Logan 5. Maya 4. Olivia 3. Ethan 2. Noah 1. Leah

In fact, the `example.txt`

file contains exactly this
example, so for this one you could just run
`java TopK 10 < example.txt`

.

**Note**: I *will* test your code on more
stringent examples than this, and I *will* use different
test programs that make heaps larger than size 10. So you should
test your own code like that as well!