Time complexity
Find min: O(logN)
Merge: O(logN)
Insert: average time is const, worst case is O(N)
A binomial queue of N elements can be built by N successive insertions in O(N) time.
$T_{worst} = O(log N),$ but $T_{amortized} = 2$
methods
left-child-next-sibling
the new tree will be the largest
maintain the subtrees in decreasing order
code
1 |
|