Isn’t the best case for heap sort O(n)?
All sources I've seen say O(nlogn) regardless of best/worst case. But I don't understand why. The best case for heap sort is when all the elements are equal. In this case, no max heapifying needs to be done.
To build the heap from the sequence is still O(n) because you don't know that you don't need to rebalance so you still have to run maxHeapify on all nodes from n/2 to 1.
Next, to extract the nodes, you swap with the last leaf then maxHeapify. However, in this case we wouldn't need more than two calls to maxHeapify because when we compare the left and right child of the root node, we see that neither are larger (they are all equal) so the procedure stops right there. These two comparisons are O(1).
As an example, if we have an input of
where the rows of numbers correspond to heights and the two bottom 3s are children of the first. After we extract the root and put the last leaf on top the tree looks like
With one comparison (at most 2 if our heap were larger), we can see that no swapping needs to be done. Whereas if we had an input of
And we extract 5 to get
We'd need to not only check that the child is larger, swap, then continue to check and potentially swap all the way down to the leaf. When all the elements of the heap are equal, you don't have to do this.
Does this make sense?
Submitted July 16, 2017 at 04:26PM by eatingpoopinrobarts
via reddit http://ift.tt/2uoH8lu