Re: [boost] [heap] A few questions

Subject: Re: [boost] [heap] A few questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-10 13:34:08

> > >   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.

it depends on the heap layout ...

> > >   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. 

in general people are adviced to specify the direction of the update. if they 
know they will only increase or decrease the key, they should use that version.

for `update(handle_type), value_type)' the effect is less crucial, since it 
mainly avoids one comparison inside `update'. for `update(handle_type)' there is 
no way to find the direction of the update, so some implementations will use a 
worse codepath than actually required ...

> 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.

that is my main idea :)

cheers, tim