Assignment 8: Heaps

Design due Wednesday 18 November, Plan due Friday 20 November, Implementation due Monday 23 November.

Reading: Standish Chapter 8.1 - 8.3 and 8.5

In this assignment you will build an implementation of a heap based on the linked tree data structure we saw on the exam. You will use this implementation to sort the lines in a file. Each line will contain an exam score (an integer) and a student's name. You program will output the lines from the file in descending order accoring to exam score.

Here are the pieces you will need to assemble:

1.

The Tree code at http://rocky.colby.edu/cs231/code/Tree/Tree.java

2.

The code for reading files that we used a couple of assignments ago:

http://rocky.colby.edu/cs231/code/Eval/Eval.java

3.

The algorithm explained in Chapter 8.5.

4.

Your own algorithm for inserting something into a Heap.

The end result should be two class definitions, Heap and Sorter. Sorter will contain main and inputLoop and will use a Heap object to store and sort the items from the file.