Binomial Heap
A forest of binomial trees supporting O(log n) merge.
Decision · step 2 of 15Binomial 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.
What you will see
Trees of sizes 1, 2, 4, ... merge like binary addition with carries.
Cost
| insert | O(1) amortized |
|---|---|
| extract min | O(log n) |
| merge | O(log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Related
Taught by the same lesson
Binomial and Fibonacci Heaps covers these too, in the same run.