Extract Min / Max
Take the root, move the last leaf up into it, then let that value sink.
Binary Heap: Extract the minimum
1 leaves. The last leaf 6 jumps to the root, which keeps the tree complete but almost certainly breaks the heap.
Cost
- Best
- O(log n)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(1)
Before this
Variants
- Extract Min
- Extract Max
Leads to
Topics that need this one first.
Taught by the same lesson
Binary Heap covers these too, in the same run.