Subject: Re: [boost] [review] Heaps: Mergeable Heaps
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-07 04:31:09
> >>> 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.
right ... on my todo list ...
tim