Heap Operations — Insert & Extract

In our emergency room analogy, we've learned how to triage incoming patients efficiently. But the critical moment isn't arrival—it's when a treatment room opens and we must instantly identify and summon the most critical patient. This is the extract operation: removing the highest-priority element while maintaining the heap's ability to serve the next highest priority immediately after.

The extract operation is the raison d'être of priority queues. Without efficient extraction, heaps would be merely an interesting data structure exercise. It's the O(log n) extraction that makes heaps indispensable for algorithms like Dijkstra's shortest path, Huffman encoding, and event-driven simulations.

In this page, we'll dissect the extraction algorithm with the same rigor we applied to insertion. We'll understand why we swap the root with the last element, how the bubble-down (heapify-down) process differs from bubble-up, and why the algorithm must choose between children—a complexity not present in insertion.

Before examining the extraction mechanics, let's establish why the root is special and why we'd ever want to remove it.

The Root Is the Extreme Value

The heap property guarantees that the root contains:

• Max-heap: The maximum value in the entire heap
• Min-heap: The minimum value in the entire heap

This follows directly from the heap property's transitivity. In a max-heap:

• Root ≥ both children
• Each child ≥ their children
• Therefore: Root ≥ all descendants = all elements in the heap

Why Remove the Maximum/Minimum?

This is exactly what priority queues need! Common use cases:

1. Task Scheduling: Always process the highest-priority task next
2. Event Simulation: Always process the earliest event first
3. Dijkstra's Algorithm: Always expand the node with the smallest tentative distance
4. Huffman Encoding: Always merge the two trees with the smallest frequencies
5. K-Way Merge: Always output the smallest among K current elements

In each case, we need the extreme value, and once we've processed it, we need the next extreme value ready immediately.

Removing the root creates a fundamental problem: we now have a "hole" at the top of the tree. Let's consider why naive approaches fail.

Attempted Strategy 1: Promote a Child Directly

We could promote one of the root's children to become the new root. But which one? And after we move it, its old position is now a hole. We'd need to recursively fill holes, and this process could affect many nodes in complex patterns, potentially degrading to O(n).

Worse, this disrupts the complete binary tree property. If we keep promoting from the same subtree, we get an unbalanced structure that's no longer a valid heap shape.

Attempted Strategy 2: Shift Everything Up

We could try to shift all elements up one position in some ordering. But heaps aren't sorted arrays—there's no simple "shift" that preserves the heap property.

The Elegant Solution: Swap with Last, Then Fix

The heap's solution mirrors insertion but in reverse:

1. Save the root value (we'll return it)
2. Move the last element to the root (this maintains the complete tree shape)
3. Bubble-down to restore the heap property (this fixes the ordering)

By moving the last element (the rightmost node at the bottom level) to the root, we:

• Remove exactly one leaf (maintaining shape)
• Create exactly one violation (new root might be smaller than children)
• Fix with a single downward path

The bubble-down algorithm (also called heapify-down, sift-down, down-heap, or percolate-down) is more complex than bubble-up because it must choose between two children.

Algorithm: Bubble-Down for Max-Heap

BUBBLE-DOWN(heap, index, heap_size):
    while true:
        largest = index
        left_child = 2 * index + 1
        right_child = 2 * index + 2
        
        # Check if left child exists and is larger than current
        if left_child < heap_size and heap[left_child] > heap[largest]:
            largest = left_child
        
        # Check if right child exists and is larger than current largest
        if right_child < heap_size and heap[right_child] > heap[largest]:
            largest = right_child
        
        # If a child is larger, swap and continue
        if largest != index:
            swap heap[index] and heap[largest]
            index = largest
        else:
            break  # Heap property satisfied

The Complete Extract Operation:

EXTRACT-MAX(heap):
    if heap is empty:
        error "Heap underflow"
    
    max_value = heap[0]           # Save root
    heap[0] = heap[heap_size - 1] # Move last to root
    heap_size = heap_size - 1     # Shrink heap
    
    if heap_size > 0:
        BUBBLE-DOWN(heap, 0, heap_size)
    
    return max_value

Why Must We Choose the Larger Child?

This is a subtle but critical point. When bubbling down, we must swap with the larger of the two children (in a max-heap). Here's why:

Scenario: Current node at index has value 30. Left child has value 50. Right child has value 40.

If we swap with the smaller child (40):

• Parent becomes 40
• Right child becomes 30
• Left child remains 50
• Result: 40 < 50, violating heap property!

If we swap with the larger child (50):

• Parent becomes 50
• Left child becomes 30
• Right child remains 40
• Result: 50 > 40 and 50 > 30. Heap property satisfied at this level!

Swapping with the larger child guarantees that the new parent is larger than both children, not just the one we swapped with. This is why bubble-down is slightly more complex than bubble-up (which has no such choice).

Let's trace through a complete extraction example with a max-heap.

Initial Max-Heap (array representation):

Index:  0   1   2   3   4   5   6   7
Value: [95, 90, 80, 70, 40, 50, 60, 30]

Tree visualization:

           95
         /    \
       90      80
      /  \    /  \
     70  40  50  60
    /
   30

Operation: ExtractMax (remove and return 95)

Final Max-Heap (array representation):

Index:  0   1   2   3   4   5   6
Value: [90, 70, 80, 30, 40, 50, 60]

Final tree visualization:

           90
         /    \
       70      80
      /  \    /  \
     30  40  50  60

Observations:

• The smallest element (30) was placed at the root and sank to become a leaf
• At each step, we swapped with the larger child to maintain the heap property
• The element traveled from the top (index 0) to a leaf (index 3)
• The heap property is now satisfied at every node
• The new maximum (90) is correctly at the root, ready for the next extract

Let's rigorously prove that bubble-down correctly restores the heap property after we've placed the last element at the root.

Loop Invariant for Bubble-Down:

At the start of each iteration, the array heap[0..n-1] satisfies the max-heap property everywhere EXCEPT possibly at node index, which might be smaller than one or both of its children. All other parent-child relationships satisfy the heap property.

Initialization (after moving last element to root):

After we place the last element at position 0:

• The element at position 0 might be smaller than its children (violation possible)
• All other nodes haven't changed position, so their relationships with children remain valid
• All nodes' relationships with their parents remain valid (we only touched the root)

✓ Invariant holds initially with index = 0.

Maintenance (each iteration preserves the invariant):

Suppose the invariant holds at the start of an iteration with current position i = index.

Case 1: heap[i] is greater than or equal to both children (or has no children)

No violation exists at position i. Combined with the invariant (no violations elsewhere), the entire heap is valid. The loop terminates. ✓

Case 2: heap[i] is smaller than at least one child

Let largest be the index of the larger child. We swap heap[i] and heap[largest].

After the swap:

1. Position i now satisfies heap property — The larger child's value is now at i. Since we chose the larger child: new_heap[i] = old_heap[largest] ≥ old_heap[other_child] = new_heap[other_child]. Also, new_heap[i] > old_heap[i] = new_heap[largest]. So i ≥ both children. ✓

2. Position largest might violate — The old value of i is now at position largest. This value might be smaller than the children at largest. This is the new potential violation point.

3. The subtree rooted at the non-swapped child is unchanged — We didn't touch it.

4. All ancestor relationships are valid — The value at i increased (or stayed same if equal), so the parent of i (if any) still satisfies heap property.

We update index = largest. The only possible violation is now at the new index.

✓ Invariant maintained.

Termination:

The loop terminates when either:

1. The index has no children (the bubbling element is now a leaf)
2. The element is greater than or equal to both children (no violation)

In both cases, the invariant holds and there's no remaining violation, so the entire heap satisfies the max-heap property.

✓ Algorithm is correct.

Termination Guarantee:

The loop must terminate because:

• Each iteration increases index (we always move to a child)
• Child indices are always greater than parent indices (2i + 1 > i for i ≥ 0)
• Index is bounded by heap size
• Therefore, we'll eventually reach a leaf or satisfy the termination condition

The time complexity of heap extraction is O(log n) in the worst case. Let's analyze each component.

Step 1: Save Root — O(1)

Accessing heap[0] is constant time.

Step 2: Move Last to Root — O(1)

Accessing the last element and placing it at index 0 are both constant time. Shrinking an array (decrementing size or popping) is typically O(1).

Step 3: Bubble-Down — O(log n)

The bubble-down loop executes at most h times, where h is the height of the heap.

Height Analysis:

For n elements:

• Height h = ⌊log₂(n)⌋
• Maximum iterations = h (from root to deepest leaf)
• Each iteration: 2 child index calculations + 2-3 comparisons + possibly 1 swap = O(1) work

Work Per Iteration:

Each iteration of bubble-down performs:

• 2 child index calculations (O(1) arithmetic)
• Up to 2 comparisons with children (O(1) each)
• At most 1 swap (O(1))
• 1 index update (O(1))

Total work per iteration: O(1), with a constant factor of roughly 5-7 operations.

Combined Complexity:

Total time = O(1) for save + O(1) for move + O(log n) × O(1) for bubble-down = O(log n)

Comparison Count: Bubble-Down vs. Bubble-Up

Note that bubble-down does ~2 comparisons per level (comparing with both children), while bubble-up does only 1 comparison per level (comparing with parent). This makes bubble-down about twice as expensive per level in terms of comparisons. However, both are O(log n), so this is only a constant factor difference.

Worst Case:

The worst case occurs when the element must bubble all the way from the root to a leaf. This happens when the last element (which we move to the root) is the smallest element in the heap—common after many extractions have removed larger elements.

Let's examine production-quality extraction implementations with proper edge case handling.

Python Implementation:

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def extract_max(self):
        """Remove and return the maximum element in O(log n) time.
        
        Raises:
            IndexError: If the heap is empty.
        """
        if not self.heap:
            raise IndexError("extract_max from empty heap")
        
        # Save the maximum value to return
        max_value = self.heap[0]
        
        # Move last element to root
        last_value = self.heap.pop()  # Also shrinks the array
        
        # If heap is now empty, we're done
        if self.heap:
            self.heap[0] = last_value
            self._bubble_down(0)
        
        return max_value
    
    def _bubble_down(self, index):
        """Restore heap property by bubbling element down."""
        heap_size = len(self.heap)
        
        while True:
            largest = index
            left = 2 * index + 1
            right = 2 * index + 2
            
            # Check left child
            if left < heap_size and self.heap[left] > self.heap[largest]:
                largest = left
            
            # Check right child
            if right < heap_size and self.heap[right] > self.heap[largest]:
                largest = right
            
            # If a child is larger, swap and continue
            if largest != index:
                self.heap[index], self.heap[largest] = (
                    self.heap[largest], self.heap[index]
                )
                index = largest
            else:
                break  # Heap property satisfied

JavaScript Implementation:

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    
    extractMax() {
        if (this.heap.length === 0) {
            throw new Error("extractMax from empty heap");
        }
        
        const maxValue = this.heap[0];
        const lastValue = this.heap.pop();
        
        if (this.heap.length > 0) {
            this.heap[0] = lastValue;
            this._bubbleDown(0);
        }
        
        return maxValue;
    }
    
    _bubbleDown(index) {
        const heapSize = this.heap.length;
        
        while (true) {
            let largest = index;
            const left = 2 * index + 1;
            const right = 2 * index + 2;
            
            if (left < heapSize && this.heap[left] > this.heap[largest]) {
                largest = left;
            }
            
            if (right < heapSize && this.heap[right] > this.heap[largest]) {
                largest = right;
            }
            
            if (largest !== index) {
                [this.heap[index], this.heap[largest]] = 
                    [this.heap[largest], this.heap[index]];
                index = largest;
            } else {
                break;
            }
        }
    }
}

Edge Cases Handled:

1. Empty heap: Raises an exception (not returning null, which hides errors)
2. Single element heap: After popping, heap is empty, skip bubble-down
3. Node has only left child: Right child check safely handles right >= heap_size
4. Node has no children: Both child checks fail, loop exits immediately

Extraction has more edge cases than insertion. Here are the most common bugs:

The min-heap version extracts the minimum element and uses opposite comparisons:

Max-Heap Extract Logic:

# Find largest among current, left child, right child
if left < size and heap[left] > heap[largest]:
    largest = left
if right < size and heap[right] > heap[largest]:
    largest = right

Min-Heap Extract Logic:

# Find smallest among current, left child, right child
smallest = index
if left < size and heap[left] < heap[smallest]:
    smallest = left
if right < size and heap[right] < heap[smallest]:
    smallest = right

Why Python's heapq Uses Min-Heap:

Python's heapq module only provides min-heap operations. To simulate a max-heap, the standard trick is to negate all values:

import heapq

max_heap = []
heapq.heappush(max_heap, -10)  # Insert 10 as -10
heapq.heappush(max_heap, -20)  # Insert 20 as -20
max_value = -heapq.heappop(max_heap)  # Returns 20

This works because negating reverses the ordering: the most negative number (representing the largest original value) becomes the minimum in the min-heap.

With both insert and extract operations, we now have a complete priority queue. Let's see the full API with all essential operations:

class MaxHeap:
    """A max-heap implementation supporting priority queue operations.
    
    All operations:
    - insert(value)    : O(log n) - Add element with bubble-up
    - extract_max()    : O(log n) - Remove and return max with bubble-down
    - peek_max()       : O(1)     - Return max without removing
    - size()           : O(1)     - Return number of elements
    - is_empty()       : O(1)     - Check if heap is empty
    """
    
    def __init__(self):
        self.heap = []
    
    def insert(self, value):
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)
    
    def extract_max(self):
        if not self.heap:
            raise IndexError("extract_max from empty heap")
        max_value = self.heap[0]
        last_value = self.heap.pop()
        if self.heap:
            self.heap[0] = last_value
            self._bubble_down(0)
        return max_value
    
    def peek_max(self):
        if not self.heap:
            raise IndexError("peek_max from empty heap")
        return self.heap[0]
    
    def size(self):
        return len(self.heap)
    
    def is_empty(self):
        return len(self.heap) == 0
    
    def _bubble_up(self, index):
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[index] > self.heap[parent]:
                self.heap[index], self.heap[parent] = \
                    self.heap[parent], self.heap[index]
                index = parent
            else:
                break
    
    def _bubble_down(self, index):
        size = len(self.heap)
        while True:
            largest = index
            left = 2 * index + 1
            right = 2 * index + 2
            if left < size and self.heap[left] > self.heap[largest]:
                largest = left
            if right < size and self.heap[right] > self.heap[largest]:
                largest = right
            if largest != index:
                self.heap[index], self.heap[largest] = \
                    self.heap[largest], self.heap[index]
                index = largest
            else:
                break

Usage Example:

# Emergency room triage simulation
er = MaxHeap()  # Higher priority = more urgent

# Patients arrive
er.insert(3)   # Minor injury
er.insert(9)   # Cardiac arrest (!)
er.insert(5)   # Broken bone
er.insert(7)   # Severe bleeding
er.insert(2)   # Common cold

# Treat patients in priority order
while not er.is_empty():
    priority = er.extract_max()
    print(f"Treating patient with priority {priority}")

# Output:
# Treating patient with priority 9
# Treating patient with priority 7
# Treating patient with priority 5
# Treating patient with priority 3
# Treating patient with priority 2

This is the essence of a priority queue: elements go in with priorities, and they come out in priority order, regardless of insertion order.

We've thoroughly examined heap extraction—the operation that makes heaps useful as priority queues. Let's consolidate the key takeaways:

What's Next:

We've now mastered both fundamental heap operations. The next page provides a rigorous time complexity analysis, cementing our understanding of why both insert and extract achieve O(log n) performance and comparing heaps to alternative data structures for priority queue implementation.