BUILD-MAX-HEAP running time for array sorted in de

Question

I know that the running time for BUILD-MAX-HEAP in heap sort is O(n). But, if we have an array that already sorted in a decreasing order, why do we still have O(n) for the running time of BUILD-MAX-HEAP?
Isn't it supposed to be something like O(1)? It's already sorted from the maximum value to the minimum value, so we do not need MAX-HEAPIFY.

Is my understanding correct? Could someone please explain it to me?

Answer 1

If you know that the array is already sorted in decreasing order, then there's no need to sort it. If you want it in ascending order, you can reverse the array in O(n) time.

If you don't know whether the array is already sorted, then it takes O(n) to determine if it's already reverse sorted.

The reason building a max heap from a reverse-sorted array is considered O(n) is that you have to start at item n/2 and, working backwards, make sure that the element is not smaller than its children. It's considered O(n) even though there are only n/2 checks, because the number of operations performed is proportional to the total number of items to be checked.

It's interesting to note, by the way, that you can build a max-heap from a reverse-sorted array faster than you can check the array to see if it's reverse sorted.

Answer 2

You are right. It can of course be O(1). When you know for sure that your list is sorted you can use it as your max heap.

The common implementation of a heap using array uses this behavior for its elements position:

childs[i] = 2i+1 and 2i+2
parent[i] = floor((i-1)/2)

This rule applies on a sorted array. (descending for max-heap, increasing for min-heap).

Please note that if you need to check first that the list is sorted it is of course still O(n).

EDIT: Heap Sort Complexity
Even though the array might be sorted and building the heap might actually take O(1). Whenever you perform a Heap Sort you will still end up with O(n log n).
As said in the comments, Heap Sort is performing n calls to extract-max. Each extraction operation takes O(log n) - We end up with total time complexity of O(n log n).
In case the array is not sorted we will get total time-complexity of O(n + nlogn) which is still O(n log n).