Complexity Analysis

Building the heap

As mentioned in the previous lesson, the time complexity of building a heap is $O(N)$. This is not obvious right away so let’s analyse the algorithm.

The entire building of the heap can be expressed as $N$ heapify events. Each heapify event take $O(h)$ time where $h$ is the height of the tree.

When I say heapify in this lesson, I mean the top to bottom heapify, the same can be proved for the bottom to up heapify as well.

Each heapify event can be provided with a tighter upper bound than $h$. For example, for leaf nodes, the heapify event is just $1$ operation since there is no node below to propagate the heapify to.

---

Number of operations

Step by step:

• $1st$ element (root): $h$ levels below it, so $h$ operations
• For the next two elements $2nd$ to $3rd$: $h-1$ operations.
• For the next four elements $4th$ to $7th$: $h-2$ operations.
• And so on…
• Second last level: 2 operations.
• Leaf nodes (last level): 1 operation.

For the sake of simplicity, let’s assume $N$ is a power of $2$ so that we work with a complete binary heap.

Also, recall that the count of nodes at any level can be expressed in terms of $N$. Nodes halves every level as two nodes connects to one node each time to go up a level.

• Nodes in the last level (leafs) = $\frac{N}{2}$. Let’s call this level $0$.

• Nodes in the second last level i.e. level $1$ = $\frac{N}{4}$.

• Nodes in level 2 = $\frac{N}{8}$ ...