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