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