Boost logo

Boost :

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




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk