AlgoScope

Sift Up

Compare with the parent and swap while the value outranks it. One path, O(log n).

Heap algorithms, algorithm, intermediateAlso called bubble up, percolate up
Comparing 1 with its parent 7. They swap and 1 moves up one level.94821017current1 < 7
Comparing 1 with its parent 7. They swap and 1 moves up one level.94821017current1 < 7

Binary Heap: Insert climbs to the root

Decision, step 3 of 6

1 is smaller than its parent 7, so they swap.

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.