Extract Max (Sift Down)

Intuition

Back to the org chart where every manager outranks their direct reports. When the CEO leaves, you cannot leave the top seat empty, and pulling up a random person would break the rule. The trick is to move the most junior person, the last seat on the bottom row, into the CEO's chair so the tree keeps its shape. They are almost certainly too junior, so they swap with the stronger of their two reports, and keep sinking until both of their reports rank below them or they reach the bottom. That sinking is sift-down, also called heapify-down or sink.

Why the stronger child? Whoever moves up becomes the parent of the other child. Promoting the larger one guarantees it is at least as large as its sibling, so the rule holds immediately at that level. Promoting the smaller one would leave a parent smaller than its new child.

How extract-max works step by step

1. If the heap is empty, signal an error. Otherwise save heap[0], the maximum.
2. Move the last element heap[size - 1] to index 0 and decrement size. The shape is still complete.
3. Set i = 0. Compute left = 2 * i + 1 and right = 2 * i + 2.
4. Find largest among i, left and right, considering a child only if its index is less than size.
5. If largest == i, stop: the node is bigger than both children. Otherwise swap heap[i] and heap[largest] and set i = largest.
6. Repeat from step 3 and return the saved maximum.

Dry run: extract-max

Start from [60, 50, 45, 30, 20, 35, 40, 10], the heap built in the heap insert lesson.

Heapify in O(n): building a heap bottom-up

Given an unsorted array you could insert elements one by one in O(n log n). The faster way leaves the array in place and calls sift-down on every non-leaf, from the last one at index n / 2 - 1 back to the root. Leaves are already one-element heaps, so they need no work. Here is [3, 9, 2, 1, 4, 5]:

Why is that linear? About half the nodes are leaves and do zero work, a quarter sit one level up and sink at most one step, an eighth sink at most two, and so on. The total is n times the series 1/4 + 2/8 + 3/16 + ..., which converges to n. Most nodes are near the bottom where sift-down is cheap, whereas building by inserts makes the many bottom nodes do the expensive climbs.

Code

import java.util.NoSuchElementException;

public class HeapOps {
    private int[] heap;
    private int size;

    // Build a max-heap from an existing array in O(n).
    public HeapOps(int[] values) {
        heap = values.clone();
        size = heap.length;
        for (int i = size / 2 - 1; i >= 0; i--) siftDown(i);
    }

    public int extractMax() {
        if (size == 0) throw new NoSuchElementException("heap is empty");
        int max = heap[0];
        heap[0] = heap[--size];      // last leaf moves to the root
        siftDown(0);
        return max;
    }

    private void siftDown(int i) {
        while (true) {
            int left = 2 * i + 1, right = left + 1, largest = i;
            if (left < size && heap[left] > heap[largest]) largest = left;
            if (right < size && heap[right] > heap[largest]) largest = right;
            if (largest == i) return;
            int tmp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = tmp;
            i = largest;
        }
    }

    public boolean isEmpty() { return size == 0; }
}

def sift_down(a, i, size):
    while True:
        left, right, largest = 2 * i + 1, 2 * i + 2, i
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest


def heapify(a):
    """Rearrange a list into a max-heap in O(n)."""
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))


def extract_max(a):
    if not a:
        raise IndexError("extract from empty heap")
    top = a[0]
    last = a.pop()                  # remove the last leaf
    if a:
        a[0] = last
        sift_down(a, 0, len(a))
    return top


h = [60, 50, 45, 30, 20, 35, 40, 10]
print(extract_max(h), h)    # 60 [50, 30, 45, 10, 20, 35, 40]

arr = [3, 9, 2, 1, 4, 5]
heapify(arr)
print(arr)                  # [9, 4, 5, 1, 3, 2]
print([extract_max(arr) for _ in range(len(arr))])   # [9, 5, 4, 3, 2, 1]

Time and space complexity

Edge cases

• Extracting from a one-element heap: after removing the last element there is nothing to move to the root; the Python code checks if a for exactly this.
• Node with only a left child: happens at most once per heap, at the last internal node; always bounds-check right separately.
• Equal children: either choice is correct; picking the left one with a strict > comparison is conventional.
• Empty heap: decide between throwing, returning null, or returning a sentinel, and say so in an interview.
• Heapify on an array of size 0 or 1: the loop range is empty and the array is already a heap.

Common mistakes

• Swapping with the left child by default instead of the larger child, which leaves the right subtree out of order.
• Using the old size in the bounds check after removal, so the sift-down compares against a slot that is no longer part of the heap.
• Starting heapify at index 0 and moving forwards. Sift-down assumes both subtrees are already heaps, so the loop must run from the last non-leaf back to the root.
• Claiming heapify is O(n log n) in an interview. The bound is O(n); the per-node log n is only an upper bound for the few nodes near the top.
• Using a min-heap API and forgetting to negate values when the problem needs the maximum.

Variations and priority queue usage

Extract-max is the remove half of every priority queue. In Java, PriorityQueue.poll() performs exactly this sift-down on a min-heap, and new PriorityQueue<>(Collections.reverseOrder()) flips it into a max-heap. In Python, heapq.heappop sifts down on a min-heap and heapq.heapify is the O(n) bottom-up build. Combining heapify with n extractions, writing each maximum into the slot freed at the end of the array, gives in-place Heap Sort. Greedy schedulers repeatedly extract the best available option, k-way merging extracts the smallest head among k lists, and replacing the root then sifting down (heapreplace) updates a bounded top-K heap in one O(log k) step.

Related LeetCode problems

• #2542 Maximum Subsequence Score — sort by the multiplier and pop the smallest sum contributor whenever the heap exceeds k.
• #2462 Total Cost to Hire K Workers — two min-heaps over the ends of the array; each hire is one extraction.
• #215 Kth Largest Element in an Array — heapify everything, then extract k times.
• #1046 Last Stone Weight — extract the two heaviest stones, then push back the difference.
• #23 Merge k Sorted Lists — repeatedly extract the smallest list head and push its successor.
• #621 Task Scheduler — extract the most frequent remaining tasks each cooling cycle.
• #767 Reorganize String — extract the two most frequent characters at a time so equal letters never touch.

FAQ