Isn’t the best case for heap sort O(n)? via /r/learnprogramming


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

3(first)

3(second) 3(third)

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

3(third)

3(second)

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

5

3 2

And we extract 5 to get

2

3

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s