There are five parts to this problem (A,B,C,D,E). Assume you have a six-element array containing the letters:

ALISON

...which need to be sorted via Heapsort into ascending order (that is, alphabetical order: letters at the front of the alphabet are 'small',

and letters at the end are 'big').

A: Show what the (unordered) heap structure will look, based on the current arrangement of letters. (That is, show a picture before imposing a partial order.)

B: Begin running the constructHeap routine on this heap structure, showing the new arrangement of the letters in the tree after the left and right subtrees have been turned into heaps. NOTE: There may be several intermediate steps, but you are NOT required to show those!

C: Show the final arrangement of the letters after constructHeap finishes. Note that if 'S' is not at the top of the heap at this point,

you must have done something wrong, since you should now have a valid heap, not just a heap structure.

D: Now run deleteMax (only once!), and show what the resulting 5-node heap will look like after deleteMax finishes (that is, right after the call to fixHeap). Heapsort of course will call deleteMax over and over again to finish the sorting, but you are NOT required to do this; Onlly run deleteMax once.

E: Now continue with Heapsort until you run deleteMax for the second time, and show what the 6-element array will look like AT THIS POINT in the algorithm (4 elements in the heap, and 2 'sorted' elements). NOTE: you may wish to consider this a 7-element array, since E(0) is always unused. (you will have to draw and manipulate the heap structure in order to envision how the elements interact. Note that I'm asking for what the array will look like at the point where two elements are sorted and the remaining 4 are still in the heap. Show the array, not just the heap.