Heap Time Complexity Analysis

Here's a question that trips up many computer science students and programmers alike: How long does it take to build a heap from n unordered elements?

The naive answer goes like this: "Each insertion is O(log n), so n insertions must be O(n log n)." This reasoning is correct for repeated insertions—but there's a better algorithm.

The bottom-up heapify algorithm builds a heap in O(n) time. Not O(n log n). Just O(n).

This is one of the most elegant results in algorithm analysis, and understanding it deeply is a hallmark of algorithmic maturity. It demonstrates how careful analysis can reveal that an algorithm is faster than its components might suggest.

In this page, we'll prove this result rigorously, build intuition for why it works, and understand when to use heapify versus repeated insertion.

Let's first establish a baseline by analyzing the obvious approach: insert each element one at a time.

Algorithm: Build Heap by Insertion

BUILD-HEAP-BY-INSERTION(array):
    heap = empty heap
    for each element x in array:
        heap.insert(x)
    return heap

Complexity Analysis:

• Insert element 1: heap size = 1, cost = O(log 1) = O(0) = O(1)
• Insert element 2: heap size = 2, cost = O(log 2) = O(1)
• Insert element 3: heap size = 3, cost = O(log 3)
• ...
• Insert element k: heap size = k, cost = O(log k)
• ...
• Insert element n: heap size = n, cost = O(log n)

Total cost:

T(n) = Σ log₂(k) for k from 1 to n
     = log(1) + log(2) + log(3) + ... + log(n)
     = log(n!)
     ≈ n log(n) - n + O(log n)    [by Stirling's approximation]
     = O(n log n)

The table shows that the sum of logarithms closely tracks n log n for large n. This confirms that the naive approach is genuinely O(n log n).

Why This Matters:

For n = 1 million elements:

• Naive approach: ~19 million operations
• Optimal approach (heapify): ~2 million operations

That's nearly a 10× difference! For real-time systems or large datasets, this difference can be the deciding factor between an algorithm that works and one that fails.

The key insight of heapify is to build the heap from the bottom up rather than from the top down. Instead of inserting elements into a growing heap, we start with all elements in an array and "heapify" each subtree starting from the bottom.

Algorithm: Bottom-Up Heapify

BUILD-HEAP(array):
    n = array.length
    
    // Start from the last non-leaf node
    // The last non-leaf is at index (n/2) - 1
    for i from (n/2 - 1) down to 0:
        BUBBLE-DOWN(array, i, n)

Why Start at (n/2 - 1)?

In a complete binary tree with n nodes:

• Nodes at indices n/2 to n-1 are leaves (they have no children)
• Leaves are already valid heaps (trivially, a single node satisfies the heap property)
• The last non-leaf node is at index (n/2) - 1

We don't need to call bubble-down on leaves because there's nothing to bubble down to!

Visualization of the Algorithm:

Consider array: [4, 10, 3, 5, 1, 8, 7]

        4 (index 0)
       / \
     10   3 (indices 1, 2)
    / \   / \
   5   1 8   7 (indices 3, 4, 5, 6)

n = 7, so we start at index (7/2) - 1 = 2.

Step 1: Bubble-down at index 2 (value 3):

• Children: 8 (index 5), 7 (index 6)
• 3 < 8, so swap with 8
• Array: [4, 10, 8, 5, 1, 3, 7]

Step 2: Bubble-down at index 1 (value 10):

• Children: 5 (index 3), 1 (index 4)
• 10 > 5 and 10 > 1, no swap needed
• Array unchanged

Step 3: Bubble-down at index 0 (value 4):

• Children: 10 (index 1), 8 (index 2)
• 4 < 10, so swap with 10
• Array: [10, 4, 8, 5, 1, 3, 7]
• Continue at index 1: children 5, 1; 4 < 5, swap with 5
• Array: [10, 5, 8, 4, 1, 3, 7]
• Continue at index 3: 4 has no children (it's now a leaf), done

Final max-heap: [10, 5, 8, 4, 1, 3, 7]

        10
       /  \
      5    8
     / \   / \
    4   1 3   7

Now for the heart of the matter: proving that bottom-up heapify runs in O(n) time.

Setup:

Consider a complete binary tree with n nodes and height h = ⌊log₂(n)⌋.

• Level 0 (root): 1 node at height h
• Level 1: 2 nodes at height h-1
• Level 2: 4 nodes at height h-2
• ...
• Level k: 2^k nodes at height h-k
• ...
• Level h (leaves): up to 2^h nodes at height 0

Key Insight:

The cost of bubble-down for a node is proportional to its height (distance to its furthest leaf descendant), not its depth (distance to root).

• A leaf (height 0) does no work (we skip it)
• A node at height 1 does at most 1 swap
• A node at height 2 does at most 2 swaps
• ...
• The root (height h) does at most h swaps

Counting the Total Work:

At height k (measured from the bottom), there are at most ⌈n/2^(k+1)⌉ nodes.

For simplicity, let's use n/2^(k+1) (the exact analysis gives the same asymptotic result).

Total work:

T(n) = Σ (nodes at height k) × (cost for height k)
     = Σ (n / 2^(k+1)) × k    for k from 1 to h
     = (n/2) × Σ (k / 2^k)    for k from 1 to h

Evaluating the Sum:

The key is evaluating Σ k/2^k for k from 1 to ∞:

S = Σ k/2^k = 1/2 + 2/4 + 3/8 + 4/16 + ...

This is a well-known series. Let's derive it:

    S = 1/2 + 2/4 + 3/8 + 4/16 + ...
   2S = 1   + 2/2 + 3/4 + 4/8  + ...

Subtracting:
   S = 2S - S = 1 + 1/2 + 1/4 + 1/8 + ... - (the adjustments cancel nicely)

Using the standard formula for this series:

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

With x = 1/2:

Σ k / 2^k = (1/2) / (1 - 1/2)² = (1/2) / (1/4) = 2

Completing the Proof:

T(n) = (n/2) × Σ (k / 2^k)
     ≤ (n/2) × 2
     = n
     = O(n)

Therefore, heapify runs in O(n) time. □

Intuition Behind the Result:

The O(n) bound seems counterintuitive until you realize the distribution of work:

• Half the nodes are leaves: They do 0 work
• A quarter of nodes are at height 1: Each does at most 1 swap
• An eighth of nodes are at height 2: Each does at most 2 swaps
• Only 1 node (root) is at maximum height: It does at most log n swaps

The work is heavily concentrated at the bottom of the tree, where most nodes are but where each node does little work. The few nodes near the top do more work per node, but there are so few of them that their contribution is bounded.

Let's directly compare the two approaches to understand the practical difference.

Approach 1: Build by Insertion (Top-Down)

• Insert each element at the end
• Bubble-up to restore heap property
• Early insertions are cheap (small heap)
• Later insertions are expensive (large heap)
• Total: O(n log n)

Approach 2: Bottom-Up Heapify

• Place all elements in array
• Bubble-down from the bottom up
• Leaf nodes (half of all nodes) do no work
• Root does the most work, but only one root
• Total: O(n)

Why the Difference?

The key asymmetry:

• Insertion (bubble-up): Work proportional to depth from root. Deep nodes (leaves) do the most work, and there are many leaves.
• Heapify (bubble-down): Work proportional to height from bottom. Deep nodes (leaves) do no work because there's no "down" to go.

*Approximate runtimes for integer arrays on modern hardware.

When to Use Each Approach:

Use Bottom-Up Heapify when:

• All elements are known upfront
• You're converting an array to a heap
• Performance is critical
• Building a heap for heapsort

Use Repeated Insertion when:

• Elements arrive over time (streaming)
• You need the heap to be valid after each addition
• Only some elements from a stream should go in the heap
• You're implementing a priority queue with ongoing insert/extract

The Takeaway:

If you have all n elements available, always use heapify. It's O(n) versus O(n log n)—a free 10× speedup for large inputs.

Let's prove O(n) using a different approach—counting swaps by where they end up rather than where they start.

Observation:

Each swap during heapify moves an element one level down. We can count the total swaps by counting how many times elements "fall" through each level.

Counting Down-Movements:

Consider any position in the tree at depth d (distance from root). During the entire heapify process:

• An element at this position can be swapped down at most h - d times (where h is tree height)
• That element came from somewhere higher (or was there originally)

Instead of tracking individual elements, let's count edge crossings:

• Each edge in the tree can be crossed downward at most once per element that eventually ends up below it
• Total edge crossings ≤ sum over all edges of (elements that cross it)

Bounding Edge Crossings:

For each edge at depth d:

• At most n/2^d elements might cross this edge (elements from the subtree above)
• There are 2^d edges at depth d
• Total crossings at depth d: at most 2^d × (n/2^d) = n

Wait, this gives O(n × h) = O(n log n)! We need a tighter analysis.

Tighter Analysis Using Potential:

Let's define a potential function and use amortized analysis.

Potential Definition: Φ(heap) = sum over all nodes i of: height(i)

For a complete binary tree:

Φ = Σ height(i) for all nodes
  = Σ (h - depth(i))
  = n×h - Σ depth(i)

The sum of depths in a complete binary tree is approximately n × h / 2 (half the nodes are leaves at max depth, etc.).

So Φ ≈ n × h / 2 = O(n log n) initially.

However, this approach needs refinement for heapify. Let's use a different counting.

Direct Counting by Level:

Each element at height k can fall at most k levels. There are roughly n/2^(k+1) elements at height k.

Total falls:

Σ (n/2^(k+1)) × k = (n/2) × Σ k/2^k = (n/2) × 2 = O(n)

This confirms our earlier result using a slightly different framing.

A natural question arises: if heapify is O(n), why is repeated insertion O(n log n)? Can't we somehow optimize insertion to get O(n)?

The Fundamental Difference:

Insertion (Bubble-Up):

• New element starts at the bottom (a leaf position)
• It must travel UP to find its place
• Work is proportional to DEPTH (distance from root)
• Leaves (half the nodes) are at maximum depth
• Late insertions cost O(log n) each

Heapify (Bubble-Down):

• Elements start at their array positions
• They travel DOWN to find their places
• Work is proportional to HEIGHT (distance to furthest leaf)
• Leaves (half the nodes) have HEIGHT 0
• Most elements do minimal work

The Mathematical Asymmetry:

In a complete binary tree:

• Sum of all depths = O(n log n)
• Sum of all heights = O(n)

This is because depths and heights are "opposite" views of the same tree, but the distribution matters.

• Depth: Many nodes (leaves) are deep → large sum
• Height: Many nodes (leaves) have zero height → small sum

Can We Use Bottom-Up for Insertion?

No, because insertion is inherently top-down from the perspective of the heap invariant:

1. A new element is placed at the end (maintaining complete tree structure)
2. This element might violate the heap property WITH ITS PARENT
3. We can't bubble-down; there are no children below the new element
4. We must bubble-up, checking against ancestors

The Constraint of Online Insertion:

Insertion is an "online" operation—each element must be positioned before the next arrives. We can't look ahead to see what's coming.

Heapify, by contrast, is "offline"—we have all elements and can process them in any order we choose. By choosing bottom-up order, we minimize total work.

Theoretical Lower Bound:

For comparison-based construction of a heap from n elements:

• Lower bound: Ω(n) — we must at least examine each element
• Upper bound: O(n) — achieved by heapify
• This is optimal!

For insertion-based construction:

• The Ω(n log n) lower bound comes from the information-theoretic argument that we're essentially sorting (determining the relative order of elements)

Let's examine production-quality implementations of the heapify algorithm.

Python Implementation:

def heapify(arr: list) -> None:
    """
    Transform arr into a max-heap in-place in O(n) time.
    """
    n = len(arr)
    
    # Start from the last non-leaf node and work backwards
    # Last non-leaf is at index (n // 2) - 1
    for i in range((n // 2) - 1, -1, -1):
        _bubble_down(arr, i, n)

def _bubble_down(arr: list, index: int, heap_size: int) -> None:
    """
    Bubble down element at index to restore heap property.
    Assumes both subtrees are already valid heaps.
    """
    while True:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < heap_size and arr[left] > arr[largest]:
            largest = left
        if right < heap_size and arr[right] > arr[largest]:
            largest = right
        
        if largest != index:
            arr[index], arr[largest] = arr[largest], arr[index]
            index = largest
        else:
            break

# Usage:
data = [4, 10, 3, 5, 1, 8, 7]
heapify(data)
print(data)  # [10, 5, 8, 4, 1, 3, 7]

JavaScript Implementation:

function heapify(arr) {
    const n = arr.length;
    
    // Start from last non-leaf and work backwards
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        bubbleDown(arr, i, n);
    }
}

function bubbleDown(arr, index, heapSize) {
    while (true) {
        let largest = index;
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        
        if (largest !== index) {
            [arr[index], arr[largest]] = [arr[largest], arr[index]];
            index = largest;
        } else {
            break;
        }
    }
}

Key Implementation Notes:

1. In-place transformation: The array is modified directly; no extra space needed
2. Starting point: (n/2) - 1 is the last non-leaf; earlier indices are also non-leaves
3. Loop direction: We go from (n/2) - 1 down to 0, ensuring children are heapified before parents
4. The heap_size parameter: Important for heapsort, where we shrink the heap during extraction

The O(n) heapify has important applications beyond simple heap construction.

Application 1: Heapsort

Heapsort consists of two phases:

1. Build a max-heap from the array: O(n)
2. Repeatedly extract max, placing it at the end: O(n log n)

The O(n) heap construction makes heapsort's total complexity O(n log n) with a good constant factor for the first phase.

Application 2: Finding the Kth Largest Element

One algorithm for finding the kth largest:

1. Build a max-heap from all n elements: O(n)
2. Extract max k times: O(k log n)

For k << n, this is O(n) dominated by the heap construction.

Alternatively:

1. Build a min-heap from the first k elements: O(k)
2. For each remaining element, if larger than heap min, replace and bubble down: O((n-k) log k)

This gives O(n log k), which is better when k is small.

Application 3: External Sorting / Merge Phase

When merging k sorted runs in external sorting:

1. Create a min-heap of k elements (one from each run): O(k)
2. Repeatedly extract min and insert next from that run: O(n log k) for n total elements

The heap construction phase is O(k), not O(k log k).

Application 4: Median Maintenance

For finding the running median of a stream:

1. Initial batch: heapify a max-heap of smaller half, min-heap of larger half: O(n)
2. Ongoing updates: O(log n) per new element

The O(n) initial construction enables efficient bootstrapping from existing data.

Application 5: Priority Queue Initialization

When creating a priority queue from known initial data:

• Library constructors often use heapify internally
• Java: new PriorityQueue<>(existingCollection) uses O(n) construction
• Python: heapq.heapify(list) transforms in-place in O(n)

Application 6: Huffman Coding Initialization

Huffman coding for data compression:

1. Create a min-heap of character frequencies: O(k) for k unique characters
2. Repeatedly merge the two smallest: O(k log k)

For large alphabets, the O(k) construction matters.

We've explored one of the most elegant results in algorithm analysis—the O(n) heap construction. Let's consolidate the key insights:

What's Next:

With insert (O(log n)), extract (O(log n)), and build (O(n)) analyzed, we have a complete picture of heap operation complexities. In the final page of this module, we'll synthesize these results to answer: Why are heaps the ideal data structure for priority queues? We'll compare heaps with alternatives and establish when heaps are the right choice.