all heaps are mergable, but with different performance constraints. so maybe a LogNOrBetterMergableHeap concept would be more expressive?

That is a terrible name for a concept :) All heaps can be merged in the same way that the distance between iterators can be computed. 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); } Or whatever... moves would probably be more appropriate if r is being torn down. 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. A better analogy might actually be a range-based find() algorithm that calls find_if for Sequences and r.find(x) for Sets (set, unordered_set,etc.). You can always find an object in a sequence, but some data structures lend themselves towards efficient operation.

...

This poses a serious problem, however. the mutable priority queue wrapper is only used to make container adaptors mutable ... these are b-heaps and d-ary heaps. fibonacci-heaps for example are can be merged (using merge_and_clear) in O(1).

I see. That wasn't abundantly clear from scanning the implementation. Thanks for clearing that up. Andrew

...

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

Andrew Sutton <asutton.list <at> gmail.com> writes:

...

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.

FWIW, I also found Heap::merge() and Heap::merge_and_clear() «somewhat odd» and was left wondering why not overload ::insert() (which copies elements from a source) and reuse splice() name from std::list<> which moves nodes from one container to the other. Best Regards, Bernard

...

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

äh ... actually this is not as straight-forward as i thought, since boost.heap iterators cannot be used to iterate the heap in the order of the nodes. so in fact we need to copy the heap and sequentially extract the top node ... tim

...

I think you should define a MergeableHeap that describes heaps that can be merged in O(log n) (i.e., binomial, fibonacci, pairing, skew). Actually, the only heaps that don't satisfy this requirement are binary heaps, b-heaps and d-ary heaps (they all seem to be linear). This is similar to the the AdjacencyMatrix in the BGL.

For binomial heaps, O(log max(x.size(), y.size())). O(1) for the others. Andrew

Right. But I want the docs to clearly state that.

Indeed they should :) Andrew