Heapify — Building a Heap Efficiently

When we first encounter the claim that heap construction is O(n), it seems almost too good to be true. After all, heap operations (insert, extract) are O(log n), and we're processing n elements. Shouldn't the total be at least O(n log n)?

Yet Floyd's bottom-up heapify achieves O(n). This isn't a trick or an approximation—it's a rigorous mathematical result. Understanding why requires diving into the structure of complete binary trees and applying some elegant series manipulations.

In this page, we'll prove the O(n) bound from first principles. We'll examine the exact work done at each tree level, sum the contributions, and derive a closed-form result. More importantly, we'll develop intuition for why the math works out the way it does. By the end, the O(n) complexity will feel not just proven, but inevitable given the tree's structure.

Let's establish the framework for our analysis with precise definitions.

Tree Structure:

For a complete binary tree with n nodes:

• Height h = ⌊log₂(n)⌋
• Level k (for k = 0, 1, ..., h) contains at most 2^k nodes
• Level 0 is the root; level h is the deepest level

Nodes at Each Level:

For a complete tree:

• Levels 0 through h-1 are fully filled: 2^k nodes at level k
• Level h may be partially filled

For simplicity, let's first analyze a perfect binary tree (all levels fully filled) with n = 2^(h+1) - 1 nodes. We'll then extend to general complete trees.

Work Done by HEAPIFY-DOWN:

When we call HEAPIFY-DOWN on a node at level k:

• In the worst case, the value at that node bubbles down to a leaf
• The distance to a leaf is (h - k) levels
• Each level requires O(1) work (comparisons and possibly a swap)
• Maximum work for this node: O(h - k)

Observation:

Notice the pattern in "Total Work at Level":

• Level 0: 1 × 3 = 3
• Level 1: 2 × 2 = 4
• Level 2: 4 × 1 = 4
• Level 3: 8 × 0 = 0 (leaves, skipped)

Total: 3 + 4 + 4 + 0 = 11 operations for n = 15 nodes.

Compare this to the naive approach:

• Level 0: 1 × 0 = 0
• Level 1: 2 × 1 = 2
• Level 2: 4 × 2 = 8
• Level 3: 8 × 3 = 24

Total: 0 + 2 + 8 + 24 = 34 operations.

Ratio: 34 / 11 ≈ 3× more work for naive approach.

Now let's derive the total work mathematically. For a perfect binary tree of height h:

Total Work:

T(n) = Σ (k=0 to h-1) [nodes at level k] × [max descent from level k]
     = Σ (k=0 to h-1) 2^k × (h - k)

Note: We sum to h-1 because leaves (level h) are skipped.

Substituting j = h - k:

Let j = h - k, so k = h - j. When k = 0, j = h. When k = h - 1, j = 1.

T(n) = Σ (j=1 to h) 2^(h-j) × j
     = 2^h × Σ (j=1 to h) j / 2^j

The Key Series:

We need to evaluate Σ (j=1 to h) j / 2^j.

For large h, this approaches the infinite series:

S = Σ (j=1 to ∞) j / 2^j = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ...

Evaluating the Infinite Series:

This is a classic series. Let's derive its sum.

Recall the geometric series:

Σ (j=0 to ∞) x^j = 1 / (1 - x)    for |x| < 1

Differentiating both sides with respect to x:

Σ (j=1 to ∞) j × x^(j-1) = 1 / (1 - x)²

Multiplying both sides by x:

Σ (j=1 to ∞) j × x^j = x / (1 - x)²

Substituting x = 1/2:

S = Σ (j=1 to ∞) j / 2^j = (1/2) / (1 - 1/2)²
  = (1/2) / (1/4)
  = 2

Result: The infinite series Σ j / 2^j converges to exactly 2.

This means:

Σ (j=1 to h) j / 2^j ≤ Σ (j=1 to ∞) j / 2^j = 2

Completing the Analysis:

T(n) = 2^h × Σ (j=1 to h) j / 2^j
     ≤ 2^h × 2
     = 2 × 2^h

For a perfect binary tree of height h:

n = 2^(h+1) - 1
2^h = (n + 1) / 2

Therefore:

T(n) ≤ 2 × (n + 1) / 2 = n + 1

Conclusion: T(n) ≤ n + 1 = O(n)

The total work is bounded by n + 1, which is linear in n. We have proven that Floyd's heap construction algorithm is O(n).

The mathematical proof is complete, but let's develop intuition for why the sum converges.

Intuition 1: Most Nodes Do Little Work

In bottom-up heapify:

• ~n/2 nodes are leaves: 0 work each
• ~n/4 nodes are one level above leaves: at most 1 swap each
• ~n/8 nodes are two levels above leaves: at most 2 swaps each
• ...and so on

The work is front-loaded at levels with few nodes:

Total work = n/2 × 0 + n/4 × 1 + n/8 × 2 + n/16 × 3 + ...
           = n × (0/2 + 1/4 + 2/8 + 3/16 + ...)
           = n × Σ j/2^(j+1)
           = n/2 × Σ j/2^j
           = n/2 × 2
           = n

Intuition 2: Compare to Naive Approach

In the naive (bubble-up) approach:

• ~n/2 nodes (leaves) may each bubble up log(n) levels
• Total: ~(n/2) × log(n) = O(n log n)

In the optimal (bubble-down) approach:

• ~n/2 nodes (leaves) do 0 work
• ~n/4 nodes do 1 work each
• The root does log(n) work, but there's only 1 root
• Total: O(n)

The key: The nodes that could do log(n) work are few (1 root, 2 at level 1, 4 at level 2...), while the nodes that are many do O(1) work or less.

Intuition 3: The Weighting Effect

Visualize the tree as a weight distribution:

          1 node × 3 work    = 3
         2 nodes × 2 work    = 4
        4 nodes × 1 work     = 4
       8 nodes × 0 work      = 0
                               ----
                               11 total for n=15

       vs.

          1 node × 0 work    = 0
         2 nodes × 1 work    = 2
        4 nodes × 2 work     = 8
       8 nodes × 3 work      = 24
                               ----
                               34 total for n=15

The bottom-up approach puts heavier weights (more work) on lighter objects (fewer nodes). The top-down approach does the opposite.

Intuition 4: Geometric Series Decay

The series 1/2 + 2/4 + 3/8 + 4/16 + ... converges because the denominator grows exponentially (doubles each term) while the numerator grows only linearly. The exponential beats the linear, ensuring convergence.

This is the same phenomenon that makes binary search logarithmic: doubling wins against adding.

Let's place the two approaches side-by-side mathematically to crystallize the difference.

Naive (Bubble Up) Summation:

T_naive = Σ (k=0 to h) 2^k × k
        = Σ (k=0 to h) k × 2^k

This is closely related to:

Σ (k=0 to ∞) k × x^k = x / (1-x)²   for |x| < 1

For x = 2 (outside the convergence radius!), this diverges.

For finite h:

Σ (k=0 to h) k × 2^k = 2 + (h-1) × 2^(h+1)
                     ≈ h × 2^h
                     ≈ log(n) × n
                     = O(n log n)

Optimal (Bubble Down) Summation:

T_optimal = Σ (k=0 to h-1) 2^k × (h - k)
          = 2^h × Σ (j=1 to h) j / 2^j
          ≤ 2^h × 2
          ≈ n
          = O(n)

The Fundamental Difference:

• Naive: Multiplies 2^k (exponentially growing) by k (linearly growing) → divergent-style growth
• Optimal: Multiplies 2^k by (h-k) which can be rewritten with 1/2^k (exponentially decaying) → convergent

Concrete Calculations for n = 1,048,575 (h = 20):

Naive:   Σ k × 2^k ≈ 20 × 2^20 = 20,971,520
Optimal: 2^20 × 2 = 2,097,152

Ratio: 20,971,520 / 2,097,152 = 10×

The optimal approach is 10× faster for 1 million elements. This ratio grows with log(n), meaning for larger datasets, the advantage increases.

Our analysis assumed a perfect binary tree. Let's verify that the O(n) bound holds for any complete binary tree.

General Complete Tree:

A complete binary tree with n nodes has:

• Height h = ⌊log₂(n)⌋
• Levels 0 through h-1 are fully filled
• Level h has between 1 and 2^h nodes

Upper Bound Analysis:

For any complete tree with n nodes:

Nodes at level k ≤ 2^k  for all k ≤ h

Therefore:

T(n) = Σ (k=0 to h-1) [nodes at level k] × (h - k)
     ≤ Σ (k=0 to h-1) 2^k × (h - k)

This is exactly the same summation we analyzed for the perfect tree, which we showed is O(n).

Tighter Bound:

We can show:

T(n) ≤ 2n

For any complete binary tree with n nodes.

Proof Sketch:

The number of nodes n satisfies:

2^h ≤ n < 2^(h+1)

Therefore 2^h ≤ n, so:

T(n) ≤ 2 × 2^h ≤ 2n

Conclusion: The O(n) bound holds for all complete binary trees, not just perfect ones.

Here's an elegant alternative proof that some find more intuitive. Instead of summing work by level, we count the total number of times each edge could be traversed.

Edge Counting Argument:

A complete binary tree with n nodes has exactly n - 1 edges (each non-root node has one edge to its parent).

In HEAPIFY-DOWN, each swap traverses one edge downward. We'll show that each edge is traversed at most once during the entire BUILD-HEAP procedure.

Key Observation:

When we perform HEAPIFY-DOWN on node i, the value that moves down either:

1. Stops at node i (no swap)
2. Moves to a descendant of node i

Crucially, the value at node i at the time of processing was either:

• The original value at node i (never moved down this subtree before)
• OR a value that came from an ancestor of i (and now might move down further)

Amortized Analysis:

Consider any edge (parent, child) in the tree. This edge can be traversed by a swap at most once during BUILD-HEAP, because:

1. Before we process the parent node, the edge hasn't been used for swapping in BUILD-HEAP
2. When we process the parent, at most one swap might use this edge (current value might descend)
3. After we process the parent, we only process ancestors, and any value that descends through this edge came from above and won't return

Conclusion:

Total swaps ≤ number of edges = n - 1 = O(n)

Since each swap is O(1), total work is O(n).

Visualizing the Argument:

Consider a path from root to leaf:

     A
      \
       B
        \
         C
          \
           D (leaf)

Edges: A→B, B→C, C→D

During BUILD-HEAP:
- Process D first (leaf, no HEAPIFY-DOWN—skipped)
- Process C: might swap C's value down to D (uses edge C→D at most once)
- Process B: might swap B's value down through C, D (uses B→C, maybe C→D)
- Process A: might swap A's value down through B, C, D

BUT: If a value descends through C→D during processing C, any future descent
from B or A that reaches C won't go through C→D again—different values.

The total number of times edge C→D is traversed is at most 1 per BUILD-HEAP.

Why This Works:

Each value that descends through an edge during HEAPIFY-DOWN either:

• Stays there (edge won't be used again for that value)
• Descends further (but can only go down, never up)

Since values only move down and each edge can pass a value down at most once per the entire algorithm (not per HEAPIFY-DOWN call), total edge traversals ≤ n - 1.

We've proven that bottom-up heapify is O(n). But can we do better? Is there an O(n / log n) or O(√n) algorithm?

Lower Bound Argument:

To build a heap, we must at minimum:

1. Examine each of the n elements at least once
2. Otherwise, an unexamined element could violate the heap property

Therefore, any heap construction algorithm must be Ω(n).

Conclusion:

Floyd's bottom-up heapify is asymptotically optimal. We cannot do better than O(n), and the algorithm achieves O(n).

Constant Factor Considerations:

The constant factor in O(n) matters for practical performance. Let's examine the actual constants:

• Upper bound: T(n) ≤ 2n comparisons and swaps
• Average case: T(n) ≈ 1.88n for random input (empirically observed)
• Best case: T(n) = 0 (input is already a heap)

The algorithm is not just asymptotically optimal but also has small constants.

The analysis technique we used—summing geometric series with polynomial coefficients—appears in many algorithm analyses. Let's see a few applications.

Application 1: HeapSort Complexity

HeapSort consists of:

1. BUILD-HEAP: O(n)
2. n EXTRACT-MAX operations: each O(log n)

Total: O(n) + O(n log n) = O(n log n)

The O(n) build doesn't dominate; the extracts do. But knowing build is O(n) (not O(n log n)) prevents overcounting.

Application 2: Amortized Analysis of Dynamic Arrays

When a dynamic array doubles capacity:

• Total work for n inserts = n + n/2 + n/4 + n/8 + ...
• This is a convergent geometric series ≤ 2n
• Amortized O(1) per insert

Same convergent series pattern!

Application 3: Binary Tree Traversal Counting

Counting operations in tree traversals often involves:

• Σ (nodes at level k) × (something depending on k)

Recognizing when this sum converges vs. diverges is crucial.

Application 4: Merge Sort Analysis

Merge sort's recurrence T(n) = 2T(n/2) + O(n) can be visualized as:

• Level 0: n work (one merge of n elements)
• Level 1: n work (two merges of n/2 elements each)
• Level 2: n work (four merges of n/4 elements each)
• ...

Total: n × (log n) = O(n log n) — work is constant per level, not decreasing.

Understanding this analysis has concrete implications for engineering practice.

Implication 1: Always Use Floyd's Algorithm

When building a heap from existing data, always use bottom-up heapify, not repeated insertions. The improvement is:

• 10× faster for n = 1 million
• 20× faster for n = 1 billion
• Asymptotically unbounded improvement as n grows

Implication 2: Understand Library Implementations

Most heap libraries use Floyd's algorithm internally:

• Python: heapq.heapify() — O(n), in-place, bottom-up
• Java: PriorityQueue(Collection) constructor — O(n)
• C++: std::make_heap() — O(n), bottom-up

When you call these functions, you're getting O(n) construction, not O(n log n).

Implication 3: HeapSort is Practical

With O(n) build time, HeapSort's total complexity is:

• O(n) build + O(n log n) extract = O(n log n)

Without this, HeapSort would have a 2× overhead: O(n log n) + O(n log n). The O(n) build makes HeapSort competitive with other O(n log n) sorts.

Implication 4: Batch Operations Are Efficient

Whenever you have a batch of items to process with a priority queue:

1. Collect all items first
2. Build heap in O(n)
3. Extract as needed

This is faster than inserting items one-by-one, especially for large batches.

We've completed our deep analysis of why bottom-up heapify achieves O(n) complexity. Let's consolidate everything we've learned.

Module Complete:

With this page, we've completed our journey through heap construction:

1. Page 1: Introduced the problem and motivated efficient construction
2. Page 2: Analyzed the naive O(n log n) approach and its limitations
3. Page 3: Presented Floyd's O(n) algorithm with implementations and proofs
4. Page 4 (this page): Provided rigorous mathematical analysis and intuition

You now have a complete, deep understanding of heap construction—from problem statement through algorithm design to mathematical proof. This is the gold standard of algorithmic knowledge: not just knowing what works, but why it works, and how well it works.

What's Next in Chapter 14:

Having mastered heap construction, we'll continue exploring heap applications: time complexity guarantees, min-heap vs. max-heap selection, common patterns like K-largest/smallest, and advanced applications like median maintenance and task scheduling.