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!

Answer 2

Heap sort guarantees that the time complexity is O(n*lgn) for any input.

But if you know that all elements of an array are only limited to "0" and "1", then you can sort that array in O(n) time complexity. (Try "counting sort")

Answer 3

You shouldn't sort 1's and 0's using HeapSort . There's a O(n) algo for that . (Using ES6)

const sorter = (input) => {
  let left = 0, right = input.length -1;
  while (right > left) {

    while (input[left] === 0 && right > left){
        left ++;
    }
    while (input[right] === 1 && right > left){
        right --;
    }
    if (input[left] > input[right]) {
      [input[left], input[right]] = [input[right], input[left]];
    }
    right--; left++;
  }
  return input;
}