running time of heap sort, when all elements are identical

Question

Can we say that, when all elements are identical in an array A of size n then running time of heap sort is O(n)

--> If this is the case, Is O(n) best case running time of heapsort

Answer 1

When all elements are equal building the heap takes O(n) steps. Because when element gets added to the heap after one compare O(1) we see it is in the correct position.

Removing the root is also O(1), when we swap the tail and root, the heap property is still satisfied.

All elements get added to the heap in O(n), and removed in O(n). So, yes in this case heapsort is O(n). I can't think of a better case so heapsorts best case must be O(n).

'Heapsorts best case is O(n)' means in English something like: there exists arrays of size n such that heapsort needs at most k*n compares to sort it. That's nice in theory but in practice it doesn't say much about how good or fast heapsort is.