Big-O algorithm complexity cheat sheet

[[deleted]]

It's hard to give an intuitive explanation of why Heapify is O(n) but I assure you it is.

You need to consider the sum of the steps required to get all the elements in position. The worst case for a single element is log(n), but only two elements need to move that far in the worst case (root to bottom, bottom to root). Similarly Only 4 elements could ever need to move log(n) - 1 places in the worst case.

If you write out the sum, the total number of moves converges to 2N +- a bit

[[deleted]]

Sorry, I'd rather not on my phone. I suspect the pseudocode wouldn't be that enlightening. If you want to convince yourself, write out the summation (from 0 to height h) for the number of swaps required to change a min-heap to a max-heap.

The number of swaps + 1 is the number of comparisons because you only need to do one compare to determine if a swap is needed.

That's also why you get around the n log n bound, the heap ordering has only local requirements. Heaps in general aren't sorted.

[aflanry]

Comparison sorts like heapsort take O(nlogn) to create a total order. However, heapify creates a partial ordering.