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

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

> >> 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 ...
> 
> I know it's possible for binary and I suspect b-heaps (and probably
> d-ary as well). Is that true for all other container-based heaps?

there are just two types of container-based heaps: d-ary heaps and b-heaps. 
binary heaps are d-ary heaps with an arity of 2.

> > ResultHeap merge(Heap1 const & h1, Heap2 const & h2);
> 
> I've always been of the opinion that merge was more like += than +,
> and that it's usually destructive on the RHS.
> 
> The term "heap union" is often used as a synonym for merge. What if
> merge() was a modifying operation and heap_union implements the
> version above. For Mergeable heaps, the heap_union is two copies and
> two merges.

i think the terms `merge' and `union' are more descriptive ...

> > // consume h2 via move
> > template <typename ResultHeap, typename Heap1, typename Heap2>
> > ResultHeap merge_and_consume(Heap1 const & h1, Heap2 && h2);
> 
> I think that merge() (if it modifies both arguments) should move by
> default. You're really transferring data from the RHS into the LHS. In
> fact, I think this might be one of those perfect examples of what move
> is supposed to do :)

true ... this would mean that we depend on boost::move ... but it seems that it 
has been accepted recently and is already merged into trunk ... 

> So... taking a quick look, we shouldn't call the operation merge(), we
> should call it heap_merge() to avoid ADL issues with std::merge. We
> don't want to break merge_sort :) I see two algorithms:
> 
> void heap_merge(Heap1& lhs, Heap2& rhs);
> void heap_union(const Heap1& lhs, const Heap2& rhs, Heap3& result);
> 
> The first transfers all objects owned by rhs into lhs. I think that's
> important. The second is more like std::merge (but without iterators).
> Obviously, there should be specializations for Mergeable heaps.

why pass the result by reference instead of returning it? to avoid passing a 
template argument? again, is there any guideline about this for boost libraries?

so with move we could write:
Heap1 heap_merge(Heap1 && lhs, Heap2 && rhs);
ResultHeap heap_union(const Heap1& lhs, const Heap2& rhs);
or
void heap_union(const Heap1& lhs, const Heap2& rhs, Heap3& result);

tim