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

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

> all heaps are mergable, but with different performance constraints. so maybe a
> LogNOrBetterMergableHeap concept would be more expressive?

That is a terrible name for a concept :) All heaps can be merged in
the same way that the distance between iterators can be computed.

Is the merge implementation for container adaptors the same? It might
be worthwhile implementing it is an algorithm rather than a member
function for inefficiently merged heaps.

void merge(Heap& l, Heap& r) {
  for(auto& x : r)
    l.push(x);
}

Or whatever... moves would probably be more appropriate if r is being torn down.

The operation could then be specialized for MergeableHeap types to
call the member function. Exactly like swap and distance. This has the
benefit of making all heaps operable under a merge operation, but only
efficiently mergeable heaps have a member function.

A better analogy might actually be a range-based find() algorithm that
calls find_if for Sequences and r.find(x) for Sets (set,
unordered_set,etc.). You can always find an object in a sequence, but
some data structures lend themselves towards efficient operation.

>> This poses a serious problem, however.
> 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).

I see. That wasn't abundantly clear from scanning the implementation.
Thanks for clearing that up.

Andrew