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

Subject: Re: [boost] [review] Heaps: Mergeable Heaps
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-05 19:07:21

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

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

Yes, you could :)

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

> // 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 :)

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

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.

Andrew