Typorithm · medium

Heap Extract (Sift Down)

heap-sift-downheapsbinary-heapsift-downextract-min

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Heap Extract (Sift Down)

Heaps

Extract-min saves the root, moves the last element to the top, and sinks it down past its smaller child.

The minimum sits at index 0, so removing it leaves a hole at the root.

Fill that hole with the last element, then sift it down by swapping with the smaller child.

Sinking continues until the element is no larger than both children, giving O(log n) extraction.

Root holds the minimum.

Last element fills the root, then sinks.

Swap with the smaller child.

pop() {
  const top = this.data[0];
  const last = this.data.pop();
  if (this.data.length === 0) {
    return top;
  }

  this.data[0] = last;
  let i = 0;
  const n = this.data.length;
  let swapped = true;
  while (swapped) {
    let smallest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && this.data[left] < this.data[smallest]) {
      smallest = left;
    }
    if (right < n && this.data[right] < this.data[smallest]) {
      smallest = right;
    }
    swapped = smallest !== i;
    if (swapped) {
      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }

  return top;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Save the root

The minimum is always at index 0.

const top = this.data[0]

2. Last to root

Move the final element to the root, then sink it.

this.data[0] = last

3. Child indices

Children of i are 2i+1 and 2i+2.

const left = 2 * i + 1

4. Pick smaller child

Track which of node and children is smallest.

if (left < n && this.data[left] < this.data[smallest]) {
      smallest = left;
    }

5. Sink down

Swap with the smaller child to restore order.

[this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]]

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.