Re: [boost] [heap] A few questions

Subject: Re: [boost] [heap] A few questions
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-10 03:07:54

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

>   2) What advantages to the increase() and decrease() functions provide?

efficiency: in some cases it is more efficient to call `increase' or `decrease' 
...

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

> http://tim.klingt.org/boost_heap/heap/data_structures.html
> Can you provide runtime complexity constraints for each of these data
> structures? Particularly if the mutable version has different performance
> from the standard version of each.

some people asked for a better comparison or a table of operations and 
complexity ... mutable versions of container adaptors have the same algorithmic 
complexity as non-mutable, but introduce an indirection ...

> spelling:
> For a low arity, the h[e]ight of the heap is larger

thnx

> improved wording:
> In analogy to d-ary heaps, boost-heaps also provides an mutable version at
> the cost of an indirection.
> would be better as:
> The
> b_heap_mutable<http://tim.klingt.org/boost_heap/boost/heap/d_ary_heap_muta
> ble.html> class
> stores the values inside a std::list in order to achieve mutability.

thnx

> 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