6 Jun
2011
6 Jun
'11
11:40 p.m.
Den 06-06-2011 23:48, Andrew Sutton skrev:
I think you should define a MergeableHeap that describes heaps that can be merged in O(log n) (i.e., binomial, fibonacci, pairing, skew). Actually, the only heaps that don't satisfy this requirement are binary heaps, b-heaps and d-ary heaps (they all seem to be linear). This is similar to the the AdjacencyMatrix in the BGL.
For binomial heaps, O(log max(x.size(), y.size())). O(1) for the others.
Right. But I want the docs to clearly state that. -Thorsten