Heapsort running time when input in Decreasing order sorted

What is the running time of heap sort when the input is already in reverse sorted.

Could anyone开发者_如何转开发 please explain? I'm confused..

---

It will be O(n log n) because even though the heap will be built in linear time i.e. O(n), on every iteration (n - 1 iterations in total), max element will be removed and max-heapify will be called which then will traverse till the bottom of the tree and will take O(log n) time.

Hence running time would be O(n log n)

---

I m assuming that by reverse order sorted --- U want to mean that (1)when we are using max-heapify then the input is given in ascending order & (2) when we are using min-heapify then the input is given in descending order. Right? I m taking the first one for analyzing.

Max-heap property with given input in ascending order: (See Cormen for HeapSort algorithm)

1. Build-Max-Heap: take Big-Omeag(n) more precisely. Normally It takes O(n) on any given input. But It's not contradictory, since this input causes the Build-Max-Heap algorithm to take atleast Big-Omega(n)... (see Cormen Chapter 3: Sec Big-Omega Notation).

2. The 2-5 line of the algo will take Big-Theta (n log n).

Hence T(n) = Big-Omega (n) + Big-Theta(n log n)

therefore, T(n) = Big-Omega (n log n).