Re: [boost] [heap] A few questions

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