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.
all heaps are mergable, but with different performance constraints. so maybe a LogNOrBetterMergableHeap concept would be more expressive?
This poses a serious problem, however. The mutable priority queue wrapper implements merge() as, at best, a linear operation, meaning that no mutable priority queue could model the MergeableHeap concept.
the mutable priority queue wrapper is only used to make container adaptors mutable ... these are b-heaps and d-ary heaps. fibonacci-heaps for example are can be merged (using merge_and_clear) in O(1). tim -- tim@klingt.org http://tim.klingt.org I don't write music for sissy ears. Charles Ives