Re: [boost] [heap] A few questions

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

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.

> >   2) What advantages to the increase() and decrease() functions provide?
>
> efficiency: in some cases it is more efficient to call `increase' or
> `decrease'
> ...
>
>
I wouldn't expect everyone using the library to know the intimate details of
each heap algorithm, so perhaps specifying what the 'best' way to
perform certain common operations on each heap implementation in the
documentation is a good idea. I suspect that people may try the various
implementations to see what is fastest for their use case, so anything that
can help making the best design and implementation choices easy could be
helpful.

>
> > I also have a few suggestions for improving the documentation:
> >
> > In http://tim.klingt.org/boost_heap/heap/concepts.html
> > the note:
> >   boost.heap implements priority queues as max-heaps. While many
> textbooks
> > and papers are formulated for min-heaps. Using max-heaps is consistent
> with
> > the STL heap functions, though.
> > would be better written as:
> >   boost.heap implements priority queues as max-heaps to be consistent
> with
> > the STL heap functions. This is in contrast with the typical textbook
> > design, which uses min-heaps.
>
> :) sounds better ... i am not a native speaker, so some of my sentences may
> not
> be the best english ...
>

I made a mistake in this one:
boost.heap implements priority queues as max-heaps to be consistent with the
STL heap functions. This is in contrast [to] the typical textbook design,
which uses min-heaps.

>
> > You mentioned:
> >      | please note, that you *have* to call update before modifying any
> >      | other
> >
> > node.
> > This should be made more explicit in the documentation
>
> i will extend the documentation of `mutability' and add links from the
> class
> reference of (update/increase/decrease) to the `mutability' page. that will
> hopefully make things clearer ...
>
> cheers, tim
>

Great, thanks!

Cheers!
Andrew Hundt