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

Subject: Re: [boost] [review] Heaps: Mergeable Heaps
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-05 10:33:42

> 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);
> }

well, it should be possible to implement it in O(N) instead of O(N log(N)) by 
using the heap iterators and creating a new heap ... 

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

i like about this approach that it would be possible to merge heaps of different 
types ... in fact we could have `heap operations' like merging, equivalence test 
and comparison of as heap functions ...

but i am not sure, how the interface for merge should look like ... maybe 
something like:

template <typename ResultHeap, typename Heap1, typename Heap2>
ResultHeap merge(Heap1 const & h1, Heap2 const & h2);

// consume h2
template <typename ResultHeap, typename Heap1, typename Heap2>
ResultHeap merge_and_consume(Heap1 const & h1, Heap2 & h2);

// consume h2 via move
template <typename ResultHeap, typename Heap1, typename Heap2>
ResultHeap merge_and_consume(Heap1 const & h1, Heap2 && h2);

the current Heap::merge() and Heap::merge_and_clear() are somewhat odd ...

thoughts?

tim

-- 
tim_at_[hidden]
http://tim.klingt.org
You can play a shoestring if you're sincere
  John Coltrane