CS2321 Programing Assignment: In Place Heap Sort

In this programing assignment you will implement in-place heap-sort, sorting a sequence of doubles. The program will read the sequence of doubles from standard-in and output to standard-out the heap as a tree on its side (as you did in the previous program) at each step of the sorting.  The heap should be implemented with a an array tree structure.  After the heap has been constructed and deconstructed print the sorted sequence.

An example input:

4 7 2 1 3
The output is:
Heap Insert:
4

Heap Insert:
7.0
    4.0

Heap Insert:
    2.0
7.0
    4.0

Heap Insert:
    2.0
7.0
    4.0
        1.0

Heap Insert:
    2.0
7.0
        3.0
    4.0
        1.0

Heap Remove:
    2.0
4.0
    3.0
        1.0

Heap Remove:
    2.0
3.0
    1.0

Heap Remove:
2.0
    1.0

Heap Remove:
1.0

Heap Remove:

Ordered Sequence: 1.0 2.0 3.0 4.0 7.0
 

If you implement the tree with Array Tree then most of your work is done.  You only need to implement the heap and the sorting algorithm:
  1. Build heap
  2. Deconstruct heap
You may reuse the code in the book for the heap, but I envision that you will need to make some changes.  For example the size method ought to return a size field.

There are several ways to structure the program; come to class for more hints.  Remember that your sorting should be in-place, meaning you can only use one array.  

Your comments in the program should give the cost of the methods.

After you have debugged your program put all the classes in a single file called HeapSort.java.  HeapSort should be the name of the only public class in the file.  Have fun computing and remember to submit a compiling program at least.