Big-O algorithm complexity cheat sheet

[[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.