The complete explanation of Heapify Big-O value (worst case)

The worst case number of steps needed to heapify a full heap is N - the height of the heap.
The worst case number of steps needed to heapify a heap with one node filled on the bottom is N-1
Those two bound the worst cases for all heaps, with the exact amount being N-(number_of_one_bits_in_N).

The equation for a full heap;
Let height = round_up(log2(N+1))
worst_case_steps_needed = N - height

Proving Heapify is O(N)

Start with a full heap with the maximum number of sift-downs needed for each node listed.
We note that the number of 0s is half N. The number of 1s is half the number 0s, the number 2s is half the number of 1s and so on.
You could calculate the limit of the series (N/2*0 + N/4*1 + N/8*2 + N/16*3 + ...)
But here's a probably easier to understand example.

Start with a heap of size 3.

0 0 1
By inspection we can see that the maximum number of Sift-Downs needed is 1.

Now add a row to the bottom.
None of the new cells will require sifting down, and all of the old cells will require 1 more sift down

0 0 0 0 1 1 2
In this example, we've added 4 cells, increasing N by 4, and Sift Downs by 3.
The number of cells added is always a power of 2, but the key is it's 1 more the rest of the heap.
Therefore, each row added increases N by some value, and increases the number of Sift Downs needed by 1 less than that.
0 0 1 0 0 1 0 0 1 0 0 1 2 2 3

No matter how many rows we add, the number of additional Sift Downs needed will always one less
Thus, for a full heap the number Sift Downs needed is N-height

Similar logic applies to a partially filled heap.
For example, start with size 4 heap - 3 rows, with one cell filled on the bottom row

0 0 1 2

Now fill the bottom row and add in the number of cells that were in the previous bottom row (1 in this example)

0 1 0 0 0 2 1 3
(Old cells colored yellow, and new cells colored blue for clarity)
Here, each row added increases N by some number, and increases the number of Sift Downs needed by the same number.
1 0 2 0 0 1 0 0 1 0 0 1 3 2 4 0

The worst case number of steps needed to heapify a heap with one node filled on the bottom is therefore N-1

Other partially filled heaps will have some number between N-1 and N-height.

^ UP ^    < Back <