What is the asymptotic running time of the $$\texttt{heapsort}$$ algorithm on an array of length $$n$$ that is already sorted in ascending order? What about if the array is sorted in decreasing order? In both cases, justify your answer.

The running time of HEAPSORT on an array of length that is already sorted in increasing order is O(n lgn), because even though it is already sorted, it will be transformed back into a heap and sorted.
The running time of HEAPSORT on an array of length that is sorted in decreasing order will be O(n lgn). This occurs because even though the heap will be built in linear time, every time the element is removed and HEAPIFY is called, it could cover the full height of the tree.