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