$6\mathrm{.}4-2$

Argue the correctness of HEAPSORT using the following loop invariant:

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 subar$-$

ray $A[i+1$:$n]$ contains the $n-$i largest elements of $A[1$:$n],$ sorted.