Homework 10: Implementing a heap

This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

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 10 finishers with the lowest times. 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 hw10.tar.gz and running tar xzvf hw10.tar.gz

3 Details

The TopTen.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 10, and finally prints out the contents of the heap to show the top 10 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.

When everything works, if your program is run with java TopTen 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 TopTen < 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!