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).