Re: [boost] [heap] A few questions

Subject: Re: [boost] [heap] A few questions
From: Andrew Hundt (athundt_at_[hidden])
Date: 2011-06-10 13:50:08

On Fri, Jun 10, 2011 at 11:46 AM, Thomas Klimpel <
Thomas.Klimpel_at_[hidden]> wrote:

> Andrew Hundt wrote:
> > On Fri, Jun 10, 2011 at 3:07 AM, Tim Blechmann <tim_at_[hidden]> wrote:
> >
> > > hi andrew,
> > >
> > > >   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?
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

I believe a heap is more like a partially ordered pile than an unordered
pile.

If you are attempting to perform heap sort or perform tasks in order of
priority from highest to lowest wouldn't a heap be appropriate?  In those
cases I was thinking that iterating over the heap in order of priority would
make sense as an alternative to calling pq.pop() repeatedly.

Such an iterator could make something like copying the contents of the heap
into another object such as a vector in sorted order as easy as a call to
std::copy(pq.sorted_begin(),pq.sorted_end(),std::back_inserter(vec)).
Perhaps an iterator adapter that achieves this effect would be more
appropriate?

I may be missing something important like a major performance disadvantage
or an existing way to accomplish this that is definitively better. However,
I don't think a std::map would be appropriate in all cases, since the
runtime complexity of various operations of a std::map isn't always the same
as the runtime complexity in each heap implementation.

Cheers!
Andrew Hundt