HW 8: Implementing a Heap
This is a programming homework assignment. It is due via
This homework is due Mon. 14 Nov. at 2359
The assignment is graded out of 100 points. Deductions will be assessed based on the correctness and efficiency of your solution.
You will be provided with the following files in the base directory
example.txt: an example set of inputs
TopK.java: a java class with a main method to find the Top K input
The following relevant files are found in the
MaxHeap.java: Starter code for a max-heap implementation of a priority queue. You will need to edit this file.
MinHeap.java: Starter code for a min-heap. Complete this file for the Bonus!
Additionally, you will be provided with additional, useful data
structures in the ic312 directory. In particular,
ArrayList.java may be very useful!
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.
TopK.java program is already written for you. It creates a
max-heap, reads in all the names and times, calling
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
ic312/MaxHeap.java methods to
implement the Priority Queue.
Bonus! (Replace the lowest HW grade)
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
and adjust the TopK.java program as necessary to make the
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.*
The fastest program in the class wins a tangible prize. Are you up to the challenge? I hope so. Good luck!
When everything works, if your program is run with
java TopK 10
and then the following (found in
example.txt) is typed into standard in (followed by
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: Your code will be tested on more stringent examples than this using different test programs that make heaps larger than size 10. So you should test your own code like that as well!