Binomial Heap
A forest of binomial trees supporting O(log n) merge.
Binomial and Fibonacci Heaps: Binomial insert: carries like binary addition
Insert 40 as a new B0, key 1 of 5. The forest holds none: no B0 yet, so the new tree simply joins the root list.
Cost
- Insert
- O(1) amortized
- Extract min
- O(log n)
- Merge
- O(log n)
- Space
- O(n)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Binomial and Fibonacci Heaps covers these too, in the same run.