1. Let index = length/2-1. This is the parent of the last node in the tree, i.e. list[index + 1] . . . list[length-1] are leaves
2. Convert the subtree with root of list[index] into a heap.
a. Given list[a] is root of tree, list[b] is left child (root *2 +1), list[c] is right child (root*2+2), if exists
b. Compare list[b] with list[c] to determine larger child
c. Compare list[a] with larger child. If list[a] < larger child, then swap, else already a heap
d. If swap, repeat step 2 for the subtree
3. Convert the subtree with the root of list[index-1] into a heap, repeat until list[0]
1. Swap the root with the end of the list.
2. Reheap down the list up to but do not including the previous root
3. Repeat until there is only one node in the list
Simulate the heapsort algorithm manually to sort the array:
Show all steps to
1. Make into a heap see image.
Show all steps to
2. Sort the array using the HeapSort see image.