Assignment 9: Heaps

Due Friday 12 November

In this assignment you will build an implementation of a heap based on a linked tree data structure. You will use this implementation to sort a set of random integers.

In the next assignment, we will transform your implementation into a generic ADT and use it to sort a file.

Here are the pieces you will need to assemble:

1.

An implementation of a Tree using a sentinel, which I will demonstrate in class.

2.

The algorithm explained in Chapter 8.5, which worked for their linear implementation.

3.

Your own algorithms for inserting and removing things from a linked implementation.

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