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

Subject: Re: [boost] [review] Heaps: Mergeable Heaps
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2011-06-06 19:40:14

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