AlgoScope

Sift Down

Swap with the better child while a child outranks the value. One path, O(log n).

Heap algorithms, algorithm, intermediateAlso called heapify down, percolate down
Comparing 6 with its children. The right child 2 is smaller, so the two swap.734286current6 > 2
Comparing 6 with its children. The right child 2 is smaller, so the two swap.734286current6 > 2

Binary Heap: Extract the minimum

Decision, step 3 of 5

Its right child 2 is smaller, so 6 sinks and 2 takes its place.

How binary heap works

Cost

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

Leads to

Topics that need this one first.

Taught by the same lesson

Binary Heap covers these too, in the same run.