Re: [boost] [review] Heaps: Mergeable Heaps

Subject: Re: [boost] [review] Heaps: Mergeable Heaps
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-05 09:31:27

> 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_at_[hidden]
http://tim.klingt.org
I don't write music for sissy ears.
  Charles Ives