The defining feature of a min-heap or max-heap is instant access to the extreme element: the minimum or maximum, respectively. This access is O(1)—simply read the root. But what happens when we want to remove this element? The answer lies in the extraction operation, and understanding its O(log n) complexity is crucial to appreciating why heaps are the premier data structure for priority queues.

Extraction is, in many ways, the inverse of insertion. While insertion adds at the bottom and bubbles up, extraction removes from the top and bubbles down. Yet the analysis is subtly different, and the mechanics have their own nuances.

In this page, we'll dissect the extract operation's time complexity with the same rigor we applied to insertion. We'll explore why extraction is O(log n), when the worst case occurs, and how the bubble-down algorithm compares to bubble-up in both theory and practice.

Before analyzing complexity, let's review the extraction algorithm. For a max-heap, extractMax removes and returns the maximum element (the root). For a min-heap, extractMin does the same for the minimum.

Algorithm: Extract-Max (Max-Heap)

EXTRACT-MAX(heap):
    if heap is empty:
        error "Heap underflow"
    
    max_value = heap[0]           // Save the root
    heap[0] = heap[n-1]           // Move last element to root
    remove heap[n-1]              // Decrease heap size
    BUBBLE-DOWN(heap, 0)          // Restore heap property
    return max_value

Algorithm: Bubble-Down (Heapify-Down)

BUBBLE-DOWN(heap, index):
    while true:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < n and heap[left] > heap[largest]:
            largest = left
        if right < n and heap[right] > heap[largest]:
            largest = right
        
        if largest != index:
            swap heap[index] and heap[largest]
            index = largest
        else:
            break  // Heap property satisfied

The key insight: we move the last element to the root position (maintaining complete tree structure), then bubble it down to its correct position (restoring heap ordering).

Let's dissect the extraction operation phase by phase.

Phase 1: Save the Root — O(1)

Reading heap[0] and storing it in a local variable: one memory access, constant time.

Phase 2: Replace Root with Last Element — O(1)

Copying heap[n-1] to heap[0]: two memory accesses, constant time.

Phase 3: Decrease Heap Size — O(1)

Decrementing the size counter: one operation, constant time.

Note: If using a dynamic array, we might optionally shrink capacity, but this doesn't affect the worst-case analysis (and is typically deferred).

Phase 4: Bubble-Down — O(log n)

This is where the work happens. Let's analyze it carefully.

Bubble-Down Analysis:

Work per iteration:

Total work per iteration: O(1)

Key observation: Bubble-down performs up to 2 comparisons per level (comparing with both children), while bubble-up performs only 1 comparison per level (comparing with parent only). This means bubble-down has a higher constant factor than bubble-up.

Number of iterations:

The loop terminates when:

• The element has no children (reached a leaf), OR
• The element is larger than both children (heap property satisfied)

Maximum iterations = height of tree = ⌊log₂(n)⌋

Each iteration moves down one level, and there are at most ⌊log₂(n)⌋ levels.

The worst case for extraction occurs when the element moved to the root must bubble all the way down to a leaf. Let's characterize when this happens.

Worst-Case Trigger Condition (Max-Heap):

The element at position n-1 (the last element in the array) is typically one of the smaller elements in the heap—it's at or near the leaf level precisely because it's not large enough to be higher. When we move it to the root, it's likely smaller than both of its new children.

The absolute worst case: the last element is the smallest element in the entire heap. After moving it to the root:

1. It compares unfavorably to both children (swap with larger child)
2. At the new position, still smaller than both children (swap again)
3. This continues until reaching a leaf

Worst-Case Trigger Condition (Min-Heap):

Symmetrically, if the last element is the largest in a min-heap, it must descend all the way to a leaf.

Why This Is Common:

Unlike insertion where the worst case (inserting an extremum) is a specific input pattern, the worst case for extraction is built into the algorithm. The last element is moved to the root regardless of its value. Since it's typically a small value (it was near the leaves), it almost always needs to descend multiple levels.

Formal Worst-Case Bound:

Claim: Extracting from a heap of n elements takes at most 2⌊log₂(n)⌋ comparisons.

Proof:

The element placed at the root has height h = ⌊log₂(n)⌋ levels below it.

At each level during bubble-down:

• We compare with the left child (1 comparison)
• We compare with the right child (1 comparison)
• We potentially swap and move down

Maximum comparisons: 2 × h = 2⌊log₂(n)⌋

Maximum swaps: h = ⌊log₂(n)⌋

The total time is O(log n), with the constant factor approximately 2× that of insertion.

Tightness: This bound is achieved when the last element is the minimum (for max-heap) and must descend through all levels. □

Example: Worst-Case Extraction

Consider a max-heap: [100, 90, 80, 70, 60, 50, 40]

Tree structure:

         100
        /   
      90     80
     / \    / 
   70  60  50  40

Extract-Max:

1. Save 100, replace with 40: [40, 90, 80, 70, 60, 50]
2. Bubble-down 40:
   • Compare 40 with 90, 80; swap with 90 → [90, 40, 80, 70, 60, 50]
   • Compare 40 with 70, 60; swap with 70 → [90, 70, 80, 40, 60, 50]
   • 40 is now at a leaf position (index 3), no children → done

3 comparisons × 2 per level = 4-6 comparisons, ⌊log₂(7)⌋ = 2 levels traversed.

The average-case analysis for extraction is less favorable than for insertion. Let's understand why.

The Structural Bias:

Recall that in a heap:

• The largest elements are near the root
• The smallest elements are near the leaves
• The last element (which we move to the root) is at the leaf level

This means the element we're bubbling down is biased toward being small. It's not a random element from the heap—it's specifically a leaf-level element, which is more likely to be small.

Expected Descent Depth:

For a heap of n elements with randomly distributed values:

• Elements at the last level have rank approximately uniformly distributed among the bottom 50% of values
• These elements typically belong somewhere in the bottom half of the tree
• Expected descent: approximately log₂(n)/2 to log₂(n) levels

Unlike insertion where random elements often stop early (average O(1) swaps), extraction tends to involve descent through a significant portion of the tree height.

Probabilistic Analysis:

Let's model the last element's position after a random series of insertions:

• The last element was inserted at the end
• It bubbled up until it reached its correct position
• If it bubbled up k levels, it's at height k from the bottom

For random insertions, the expected bubble-up distance is O(1), so the last element is usually still near the leaf level.

After moving to the root, this element must descend through almost all levels:

• Expected comparisons: approximately 2 log₂(n) × (fraction of height traversed)
• For random heaps, this is often 0.8 to 1.0 times the full height

Empirical Observation:

In practice, extraction consistently takes close to the worst-case time, while insertion often terminates early. This asymmetry is important for workload characterization:

• Insert-heavy workloads: better than predicted by worst-case
• Extract-heavy workloads: close to worst-case predictions
• Balanced workloads: assume O(log n) for planning

Like insertion, extraction is an in-place operation with constant auxiliary space.

Auxiliary Variables:

Total auxiliary space: O(1)

The algorithm is iterative, so there's no recursion stack overhead. Some implementations use recursion for bubble-down, which would add O(log n) stack space, but this is avoidable.

Heap Size Reduction:

After extraction, the heap has n-1 elements. If using a dynamic array:

• Immediate shrinking is typically not performed (to avoid thrashing)
• Shrinking can be deferred until size drops below capacity/4
• When shrinking occurs, it's O(n) but amortized O(1) per operation

This mirrors the resizing strategy for dynamic arrays on insertion.

The standard bubble-down performs 2 comparisons per level: one with each child. Floyd's optimization reduces this to approximately 1 comparison per level on average by changing the algorithm structure.

Standard Approach (per level):

1. Compare element with left child
2. Compare element with right child (or the larger of left/right with element)
3. Swap if necessary

Floyd's Bottom-Up Approach:

Instead of comparing at each level, descend directly to a leaf by always following the larger child:

FLOYD-BUBBLE-DOWN(heap, index):
    value = heap[index]      // Save the value being bubbled
    
    // Phase 1: Descend to a leaf, promoting children
    while 2*index + 1 < n:   // While has left child
        larger_child = 2*index + 1
        if larger_child + 1 < n and heap[larger_child+1] > heap[larger_child]:
            larger_child = larger_child + 1
        heap[index] = heap[larger_child]   // Promote child (no comparison with value)
        index = larger_child
    
    // Phase 2: Bubble the saved value up from the leaf
    // (Use standard bubble-up from the leaf position)
    heap[index] = value
    BUBBLE-UP(heap, index)

Why This Can Be Faster:

• Phase 1: Exactly 1 comparison per level (which child is larger)
• Phase 2: Usually 0-2 bubble-up steps since the value often belongs near the leaf

For elements that would go most of the way down anyway (the common case), this reduces comparisons from 2 per level to 1 per level.

Analysis of Floyd's Approach:

Worst case: Still O(log n) — we might descend all the way and then bubble almost all the way back up.

Average case: Approximately 1.5 comparisons per level instead of 2, since:

• 1 comparison per level during descent (comparing children)
• Approximately 0.5 comparisons during bubble-up (if the value belongs near the leaf)

This gives an empirical speedup of 25-33% for extraction.

Trade-offs:

When to Use:

Floyd's optimization is primarily used in heapsort (where extraction dominates) rather than in general priority queue implementations. Modern CPU branch predictors often make the difference negligible for typical priority queue workloads.

When we perform sequences of operations on a heap, the amortized analysis provides insight into overall performance.

Sequence of n Insertions Followed by n Extractions:

This is a common pattern: fill a heap, then drain it (essentially heapsort).

• n insertions: O(n log n) total in worst case, O(n) average for random input
• n extractions: O(n log n) total (each extraction is O(log n), and average ≈ worst case)

Total: O(n log n)

This matches heapsort's complexity.

Interleaved Operations:

For a workload mixing insertions and extractions:

• Each extraction removes the element that was the "best" for the queue's purpose
• Each insertion adds a new candidate
• Both operations are O(log n)

No amortization helps here—each extraction really does O(log n) work most of the time.

Comparison with Fibonacci Heaps:

Fibonacci heaps offer amortized improvements for some operations:

For applications like Dijkstra's algorithm with many decrease-key operations, Fibonacci heaps can be asymptotically faster. However, the high constant factors and implementation complexity mean binary heaps are preferred for most practical applications.

Let's examine how extraction performs in practice, beyond asymptotic analysis.

Memory Access Pattern:

During bubble-down:

1. Read heap[index] (current element)
2. Read heap[left] and heap[right] (children)
3. Write swap positions
4. Index jumps to 2index+1 or 2index+2

Cache Behavior:

• First few levels: Elements are close together, likely in L1 cache
• Middle levels: May span cache lines, some misses
• Deep levels: More spread out, cache less effective

For a heap of 1 million elements (20 levels):

• Levels 0-10: ~2000 elements, likely in L2 cache
• Levels 10-15: ~60,000 elements, L3 cache territory
• Levels 15-20: ~900,000 elements, main memory

Branch Prediction:

The bubble-down loop has branches for:

• Checking if children exist
• Comparing children to find the larger
• Comparing with parent to decide swap

For consistent workloads, branch predictors learn the pattern. For random heaps, misprediction rates increase.

Comparison Cost:

If elements are complex objects with expensive comparison:

• 2 × log₂(n) comparisons per extraction
• For n = 1 million: ~40 comparisons
• If each comparison is O(k) for string length k: total O(k log n)

*Times are approximate for integer heaps on modern hardware, assuming good cache behavior.

Optimization Tips:

1. Use contiguous memory: Array-based heaps vastly outperform pointer-based trees
2. Consider element size: For large objects, store pointers in the heap
3. Profile, don't guess: Cache effects vary by hardware
4. Batch operations when possible: For heapsort, all extractions happen in sequence—cache warms up

We've thoroughly analyzed the extraction operation's time complexity. Let's consolidate the key insights:

What's Next:

With both insertion (O(log n)) and extraction (O(log n)) analyzed, we've characterized the individual operation complexities. But there's a surprising result for heap construction: building a heap from an array of n elements takes only O(n) time, not O(n log n). In the next page, we'll explore this counterintuitive result and understand why bottom-up heapify is so efficient.