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 ...
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.
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 ... but i am not sure, how the interface for merge should look like ... maybe something like: template <typename ResultHeap, typename Heap1, typename Heap2> ResultHeap merge(Heap1 const & h1, Heap2 const & h2); // consume h2 template <typename ResultHeap, typename Heap1, typename Heap2> ResultHeap merge_and_consume(Heap1 const & h1, Heap2 & h2); // consume h2 via move template <typename ResultHeap, typename Heap1, typename Heap2> ResultHeap merge_and_consume(Heap1 const & h1, Heap2 && h2); the current Heap::merge() and Heap::merge_and_clear() are somewhat odd ... thoughts? tim -- tim@klingt.org http://tim.klingt.org You can play a shoestring if you're sincere John Coltrane