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

Subject: Re: [boost] [review] Heaps: Mergeable Heaps
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-06 06:34:33

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