AlgoScope

Extract Min / Max

Take the root, move the last leaf up into it, then let that value sink.

Heap algorithms, algorithm, intermediate
1 is removed. The last leaf 6 takes the root position, keeping the tree complete.734682current
1 is removed. The last leaf 6 takes the root position, keeping the tree complete.734682current

Binary Heap: Extract the minimum

Step, step 2 of 5

1 leaves. The last leaf 6 jumps to the root, which keeps the tree complete but almost certainly breaks the heap.

How binary heap works

Cost

Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(1)

Before this

Variants

  • Extract MinMin heap.
  • Extract MaxMax heap.

Leads to

Topics that need this one first.

Taught by the same lesson

Binary Heap covers these too, in the same run.