Prove the correctness of HEAPSORT by using the following loop invariant:

At the start of each iteration of the for loop,

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] in sorted order.