6 Jun
2011
6 Jun
'11
9:48 p.m.
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. Andrew