Extract

Remove the root, move the last up, sift down.

Extract

When extracting the root (smallest) from a heap: the last element moves to the root, the heap shrinks by one, then sift-down is done.

Sift-down: if the root is smaller than its children stop; otherwise swap with the smaller child and go down. Stop at a leaf.

Extraction is O(log n): root swap O(1) + sift-down O(log n).

Sift-down detail

Sift-down: i is the root index. Left and right children are computed. The smaller child is found. If arr[i] is larger than the smaller child, swap, set i = smaller child index, repeat.

Stop at a leaf (no children) or when <= both children. The min-heap property is restored.

Each swap goes down one level; at most log n swaps.

Exercise Sift-down (extract)

Write sift_down(arr, n, i). Sift down for a min-heap. Print [1, 3, 2] with arr = [3, 1, 2]; sift_down(arr, 3, 0); print(arr).

Show example solution

def sift_down(arr, n, i):
    # Sift down
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        sift_down(arr, n, smallest)
arr = [3, 1, 2]
sift_down(arr, 3, 0)
print(arr)

Test yourself

Extract: match the terms

Extract

Take root
Sift-down

Shift down
Smaller child

Swap
Cost

O(log n)
Which child does sift-down swap with?
- The larger one
- Right always
- Left always
- The smaller one
Show answer

The smaller one — The smaller one

Sift-down condition

if arr[smallest] ____arr[i]:

Show answer

if arr[smallest] <arr[i]:

Next lesson: Summary - Heap

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies