AlgoScope

Binomial Heap

A forest of binomial trees supporting O(log n) merge.

Data structures, data structure, expert
Insert 40: 0 links.heap40

Binomial and Fibonacci Heaps: Binomial insert: carries like binary addition

Decision, step 2 of 15

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)

Leads to

Topics that need this one first.

Taught by the same lesson

Binomial and Fibonacci Heaps covers these too, in the same run.