Heap Sort $[12$ points$]$

$1.$ Illustrate the operation of Heap$-$Sort on the array A $=[5,13,2,25,7,17,20,8,4].[3$ points$]$

$2.$ Argue the correctness of Heap$-$Sort using the following loop invariant $[4$ points$]$

At the start of each iteration of the for loop of lines $2-5,$ the subarray A$[1$:i$]$ is a max$-$heap

containing the i smallest elements of A$[1$:n$],$ and the subarray A$[$i$+1$:n$]$ contains the n $$ i

largest elements of A$[1$:n$],$ sorted.

$3.$ What is the running time of Heap$-$Sort on an array A of length n that is already sorted in increasing

order? How about if the array is already sorted in decreasing order? $[5$ points$]$