What is the running time of Heapsort when the input is an array where all key values are equal?
\Theta(n)
\Theta(n^2)
\Theta(\log n)
\Theta(n ^ n)
\Theta(n \log n)
Heapsort has the same asymptotic cost in the best, average, and worst cases, but only if the key values are all unique.
If you have a heap with all equal key values, what will the siftdown operation do?
In that case, siftdown will always return immediately,
resulting in a constant time operation. Since Heapsort calls
siftdown n
times, the total cost is \Theta(n)
.