Root removal and sift-down

After this page, you should be able to:

• Distinguish minimum inspection from removal and repair the correct child path.

• Handle empty, singleton and one-child boundaries without losing records.

Builds on: Heap representation and insertion establish the valid starting state.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

The Julia heap array starts at 1: parent=floor(i/2), children=2i and 2i+1. The support MinHeap implements heap repair rather than sorting on each removal. Stable record heaps compare priority and a unique counter before the payload; max queues negate numeric priorities.

Operation contracts¶

The full input list must be a valid min-heap for peek/pop. Duplicates are separate entries. Public record queues call the same selection idea remove_min or extract_min, but return the item rather than the priority.

Inspecting and removing are different operations¶

The root holds a minimum, so peek_min only needs to check emptiness and read index 0. Removal must additionally repair the remaining heap.

def peek_min(heap):
    if not heap:
        raise IndexError("peek at empty heap")
    return heap[0]

function peek_min(heap) {
    if (!heap.length) throw new RangeError("empty heap"); return heap[0];
}

function peek_min(heap::AbstractVector)
    isempty(heap) && throw(BoundsError())
    return heap[1]
end

Swap with the smaller child¶

Assume the two child subtrees are already valid heaps. If the current item exceeds a child, choose the smaller existing child and swap. Choosing the larger child could leave the smaller child below a parent that is still too large.

def sift_down(heap, i):
    n = len(heap)
    while 2 * i + 1 < n:
        child = 2 * i + 1
        right = child + 1
        if right < n and heap[right] < heap[child]:
            child = right
        if heap[i] <= heap[child]:
            break
        heap[i], heap[child] = heap[child], heap[i]
        i = child

function sift_down(heap, i) {
    const n = heap.length;
    while (2 * i + 1 < n) {
        let child = 2 * i + 1, right = child + 1;
        if (right < n && heap[right] < heap[child]) child = right;
        if (heap[i] <= heap[child]) break;
        [heap[i], heap[child]] = [heap[child], heap[i]]; i = child;
    }
}

function sift_down!(heap, i)
    n = length(heap)
    while 2i <= n
        child = 2i; right = child + 1
        right <= n && heap[right] < heap[child] && (child = right)
        heap[i] <= heap[child] && break
        heap[i], heap[child] = heap[child], heap[i]; i = child
    end
    return nothing
end

The loop requires a left child. A right child is compared only when its index is valid. If children tie, this code chooses the left one; it does not thereby promise stable removal of equal-priority records.

Remove the final leaf, then move its item to the root¶

def pop_min(heap):
    if not heap:
        raise IndexError("pop from empty heap")
    result = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0)
    return result

function pop_min(heap) {
    const result = peek_min(heap), last = heap.pop();
    if (heap.length) { heap[0] = last; sift_down(heap, 0); }
    return result;
}

function pop_min!(heap)
    result = peek_min(heap); last_item = pop!(heap)
    if !isempty(heap); heap[1] = last_item; sift_down!(heap, 1); end
    return result
end

Removing the last slot preserves complete shape. Moving its item to the root can violate order downwards, but the remaining child subtrees are still valid. Sift-down restores their connection to the root. Removing index 0 with pop(0) would instead shift the array and destroy this structural reasoning.

Remove 2 from the lecture heap¶

Save root 2 for return. Remove final item 6, move it into the root, then compare children 5 and 4. Choose 4 and swap. The result is [4, 5, 6, 9, 7]; return 2.

Empty, singleton and one-child cases¶

The singleton guard avoids assigning index 0 after the array becomes empty. A sift-down node with only a left child uses that child normally. At most one downward path is repaired, giving $O(\log(n+1))$ repair time and constant auxiliary space. A backing-array shrink can add an occasional copying cost; the comparison bound and allocation policy are separate claims.

Implementation choices, correctness and costs¶

Saving the old root separates the returned result from the remaining storage. Removing the final leaf preserves shape; the child-selection rule preserves heap order off the repair path. Empty pop raises before changing anything, and a singleton is removed without writing into an empty list.

Choosing the left child on a tie is deterministic but not stable record selection. The swap-based repair uses O(1) workspace; a hole-moving variant would make different assignments. Peek uses O(1) time and space; pop repairs one path in O(log(n+2)) time with O(1) workspace. A Python-list shrink can add O(n+1) time/storage work on an individual call, while ordinary geometric storage policies support amortised bounds. This differs from shifting all elements with pop(0).

Check your understanding¶

Predict the returned result and remaining heap before opening the explanation.

1. What does pop_min([4]) return and leave?

2. Why choose the smaller child during min-heap sift-down?

Next: Bottom-up construction.