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

Subject: Re: [boost] [review] Heaps: Mergeable Heaps
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-06 17:48:56

>> 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