Heap

Heapify

Heapify is the process of creating a heap data structure from a binary tree.

What blows my mind is that you can create a heap from an array in $\Theta (n)$, and not $\Theta (n\log n)$. The reason for this is that we are starting from the last value of the heap in the array.

Used in Heap Sort.

Why is it O(n)?

1. Different levels of the heap contribute differently to the total cost:

   • The bottom-most level of the heap (leaves) requires 0 sift-down operations, as they have no children.
   • The second-to-last level (parents of the leaves) requires at most 1 sift-down.
   • The third-to-last level (grandparents of the leaves) requires at most 2 sift-downs.
   • And so on, until the root, which can require at most log(n) sift-downs.

2. Fewer nodes at higher levels:

   • The number of nodes at each level decreases exponentially as you move up the heap. Specifically, half of the nodes are at the bottom-most level, a quarter are at the second-to-last level, an eighth are at the next level, and so on.

This gives rise to a summation that reflects the total work done during the heapify process:

Total work=∑i=0log⁡n(nodes at level i×sift-down cost at level i)\text{Total work} = \sum_{i=0}^{\log n} \left( \text{nodes at level i} \times \text{sift-down cost at level i} \right)Total work=i=0∑logn​(nodes at level i×sift-down cost at level i)

More concretely, we can express it as: $T(n)={\sum }_{i=0}^{\log n}\frac{n}{2^i}\times i$

Where:

• $\frac{n}{2^i}$ is the number of nodes at level $i$,
• $i$ is the maximum number of sift-down operations needed at that level.

The summation evaluates to O(n).