Heapify

Concept

Imagine you are given a completely unsorted array of numbers: [7, 3, 2, 5, 1, 8].
You need to convert this array into a valid Min-Heap.

The Naive Approach ($O(N \log N)$):
You create a brand new, empty Min-Heap. You run a for loop over the unsorted array, calling heap.insert(num) for every single item.
Because insert() takes $O(\log N)$ time, and you do it $N$ times, building the heap takes $O(N \log N)$ time.

The Optimal Approach: Heapify ($O(N)$):
There is a brilliant mathematical algorithm called Heapify (or Floyd’s Build-Heap algorithm) that can mutate the unsorted array into a perfect Min-Heap in-place, in strictly $O(N)$ time!

How Heapify Works

Instead of inserting from the top down (bubbling up), Heapify works from the bottom up (sinking down).

1. Look at the array as a Complete Binary Tree.
2. The absolute bottom half of the tree consists entirely of Leaf Nodes. (A leaf node has no children).
3. Because Leaf Nodes have no children, they are already mathematically valid heaps by themselves! We do not need to process them.
4. We start at the very last Parent Node (which is located at index Math.floor(N / 2) - 1).
5. We call bubbleDown() (Sink Down) on that parent node.
6. We decrement our index, calling bubbleDown() on every parent all the way back up to index 0 (the Root).

Because we process from the bottom up, by the time we call bubbleDown() on a node, we mathematically guarantee that its Left and Right subtrees are already perfect, stable heaps! The single out-of-place parent simply filters down through the stable subtrees into its correct resting place.

The Math Behind O(N)

Why is Heapify $O(N)$ while Insert N times is $O(N \log N)$?

It comes down to the geometry of a Binary Tree.
In a Binary Tree, the vast majority of the nodes (exactly half of them!) are at the very bottom level.

• In the Insert approach, you are taking those millions of bottom-level nodes and bubbling them UP. Bubbling up from the bottom takes the maximum number of operations ($\log N$). You are doing maximum work on the maximum number of nodes.
• In the Heapify approach, we skip the bottom level entirely! We only call bubbleDown on the upper levels. A node one level above the bottom only sinks down a maximum of 1 step. The Root node sinks down $\log N$ steps, but there is only one Root node! We do minimal work on the majority of nodes, and maximum work on the minority of nodes. The mathematical sum of this geometric series converges perfectly to $O(N)$.

Usage in Practice

In Python, this is built directly into the standard library:

import heapq

nums = [7, 3, 2, 5, 1, 8]
heapq.heapify(nums) # Mutates the array in-place in O(N) time!
print(nums) # [1, 3, 2, 5, 7, 8] (A valid Min-Heap)

In JavaScript, if you are asked to “Initialize a Heap with an existing array”, you must explain to the interviewer that you would run the $O(N)$ Heapify algorithm on the array constructor rather than manually inserting elements one by one.

Interview Questions

Q: A problem asks you to find the Kth Largest Element in an array. You decide to Heapify the entire array into a Max-Heap, and then pop() K times. What is the time complexity?
A:

1. Heapify the array: $O(N)$ time.
2. Pop K times: Each pop takes $O(\log N)$. So $K$ pops take $O(K \log N)$.
   Total Time Complexity: $O(N + K \log N)$.
   (Note: If $K$ is very small, like $K=3$, this behaves like $O(N)$. However, if $K$ is large, like $K=N/2$, this degrades towards $O(N \log N)$. In the next section, we will see an even better trick to keep it optimized!).