Built Max Heap: $[9,8,5,7,2,3,1,4,6]$

Now that the heap is built, sketch the next steps of the algorithm using 'Heap Sort', which will eventually sort the array. Draw the tree and corresponding array at each step. Please show all the work for each step till the array is sorted.