Subject: Re: [boost] [heap] A few questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-10 13:46:43
> > > > 1) Is it possible to iterate through the heap in order of
> > > >
> > > > priority with an iterator?
> > >
> > > at the moment it is not possible to iterate the heap in order ... i
> > > have been thinking that this may be useful in some cases,
> > > however this can only be
> > > achieved by increasing the complexity of iterators (in fact every
> > > iterator will
> > > require a priority queue of possible `next' objects).
> > > however it would also simplify heap comparison ...
> >
> > Also, if one wanted to go through the heap in order of priority in a
> > convenient manner without removing elements it would be very helpful.
> > The simplified heap comparison is definitely an added bonus. I'm also
> > curious how that additional priority queue internal to the iterator
> > would do in terms of memory and runtime performance.
>
> Isn't iteration in order of priority completely opposite to the very idea
> of a heap (="unordered pile")? If you want/need that, isn't a std::map
> more suitable for your use case?
actually a treap (like boost::intrusive::treap) would be the most efficient data
structure for that.
otoh, one of the ideas behind boost.heap is to emulate a specific functionality
if it is not supported out of the box. e.g. it supports merging of all heaps, no
matter if they can be merged efficiently or not ...
tim