1
$\begingroup$

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)$?

$\endgroup$
2
2
$\begingroup$

It would be $O(n)$, because each call to a siftdown or 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:

  • heapify the array ($n$ siftdown from last to first element);
  • extract each value ($n$ siftdown).

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

$\endgroup$
3
  • $\begingroup$ can you please elaborate on this? $\endgroup$ – Shubhang Gupta Apr 2 at 18:35
  • 1
    $\begingroup$ The siftup and siftdown move the current element either up or down in the heap until its in its right place. Since all elements are identical, the right place for any value could be anywhere in the heap, and thus a well-implemented siftup and siftdown would take only O(1) time (on any element it will be run on, it wont change its place), for a total of O(n) $\endgroup$ – nir shahar Apr 2 at 18:43
  • $\begingroup$ I have added some details to the explanation. If this is not enough, I recommand that you review the heap data structure and the heapsort in the general case (en.wikipedia.org/wiki/Heapsort). $\endgroup$ – Nathaniel Apr 2 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.