The running time of heapsort on an array a of length n that is already sorted in increasing order is O(n log n). This is because, in the first phase of the heapsort algorithm, the array is transformed into a heap data structure, which takes O(n) time. However, since the array is already sorted in increasing order, the heap property is already satisfied, so this step can be skipped, reducing the time complexity to O(1). In the second phase of the heapsort algorithm, the root element is removed from the heap and added to the sorted portion of the array. This step is repeated n times, with each step taking O(log n) time. Therefore, the total running time is O(n log n).
On the other hand, if the array is already sorted in decreasing order, the running time of heapsort is also O(n log n). This is because the heap data structure will need to be built in the first phase, which takes O(n) time regardless of the initial order of the array. In the second phase, each element is removed from the heap and added to the sorted portion of the array, with each step taking O(log n) time. Since the heap property is violated in the initial array, each removal operation will require the heap to be reconstructed, which also takes O(log n) time. Therefore, the total running time is still O(n log n) in this case.