Given n numbers that all are identical, then what would be the running time of heap sort?
Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
It would be $O(n)$, because each call to a
siftup procedure would be executed in $O(1)$ if well implemented.
Indeed, in a maxheap, the siftdown procedure is called in the heapify procedure, or to extract a node from the tree, and is defined as follow:
siftdown(x): while x is not a leaf and x is strictly smaller than its two children: swap x and its largest child
Since you consider an array of $n$ equal values, the test
x is strictly smaller than its two children will never be true, so the loop will never be executed and the complexity is $O(1)$.
Now, the heapsort procedure in an array of size $n$ is defined as follow:
The total complexity is indeed $O(n)$. Please note that one can prove that the heapify procedure can be executed in $O(n)$ in all cases (and not only with equal values).