What is the time complexity of sorting an array of 0s and 1s using heapsort?

Question

In heap sort, if all the elements are only 0s and 1s, will the complexity change compared to the normal case with random elements?

Answer 1

The runtime of heapsort is determined by two parts:

• The time required to build the heap, which is Θ(n), and
• The time required to continuously remove elements from the heap, which (in general) is Θ(n log n)

In the case case where all the values are 0s or 1s, it is still possible that the runtime of the second step will be Ω(n log n). Suppose that your heap is structured so that all of the elements in the bottom layer are 1s and all the elements of the other layers are 0s. In this case, the first n times that you remove an element and try to fix up the heap, you'll swap a 1 up to the root, then continuously bubble the 1 downward to the bottom of the tree, which takes time Θ(log n). This means that the work done will be at least Ω(n log n).

As @SRF pointed out, though, it's not necessary to use heapsort here. You can use counting sort to sort the array is Θ(n) time.

Hope this helps!