Question $2$ Consider the for$-$loop inside the HEAPSORT algorithm $($same pages as

the previous question.$).$

a$)$ Write an appropriate loop$-$invariant for it$.$

b$)$ Prove that your loop invariant is initially true.

c$)$ Assume the loop invariant is correct, prove that remains valid after an iteration.

d$)$ Assume the loop invariant is correct, prove the correctness of the sort algorithm at termination.

Building a heap

The Heapsort Algorithm