By hand (no program involved, nor web site): put these numbers into a heap (but show in an array) in the order given here, showing the resulting array after each addition: 65 45 70 50 85 55 60 75 80

After you create the heap, show the steps (one element at a time) to sort the heap, using the heapsort algorithm given in LESSON 10, page 10.3 (the one that creates a Max Binary Heap first).

Heap sort algorithm:

Make a binary max heap out of the elements in the array (could be a local array or re-use the input array)

The last index of the heap will start out as numElems-1 (I'll call it lastHeapIndex)

Swap the 0th element with the element in lastHeapIndex.

Decrement the lastHeapIndex (so the heap is now 1 element smaller)

Percolate down within the smaller heap (see step 4 in page 10.2 of the deletion steps).

Repeat steps 3, 4 and 5 until lastHeapIndex is 1.

Swap element 0 with element 1 and the array is now sorted!