1. Illustrate the operation of HEAPSORT on the array $A=[5,13,2, 25, 7, 17, 20, 8, 4]$.
2. Prove that an $n$-element heap has height $\lfloor \lg n\rfloor$ and has at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$.
3. Implement Heapsort.
4. What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?