Re: [boost] [gsoc] boost.heap update

Subject: Re: [boost] [gsoc] boost.heap update
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-07-29 05:34:22

hi,

thanks for looking into it ...

> * Motivation: Many boost libraries offer a "Motivation" section to say
> what real world issues are addressed by the library. Currently, I am
> using std::priority_queue and it suits my needs. When would they be
> insufficient?

true ... as for std::priority_queue. it not mutable, not stable, different 
instances cannot be merged or compared, elements cannot be iterated.

> * Navigation: Some pages are missing navigation elements, e.g.
> http://tim.klingt.org/boost_heap/heap/concepts.html should have a
> "top"-link.

hm, i just saw it too ... i guess, this is a quickbook/boostbook issue, that 
will be resolved automatically, if it becomes an official part of boost ...

> * Warnings: For instance: Mutability: "Incorrect use of increase or
> decrease  may corrupt the priority queue data structure!" It would be
> good to have short examples of correct and incorrect usage.

i am a bit afraid to show a piece of incorrect code. in the documentation. 
but is is probably clearer than just describing it with words ...

> * Data structure comparisons: The information seems rather incomplete.
> For instance, "In contrast to d-ary heaps, binomial heaps can also be
> merged in O(log n)." OK, now I know, that binomial heaps can be merged
> in O(log n), and d-ary can't. But I don't know the complexity for
> merging d-ary nor any other heap.
> Maybe it would be easier to use one or more tables to compare the
> features/complexities?

well, i have been thinking about it ... however i am not sure, what to 
compare (amortized or worst-case complexity). also the analysis of pairing 
heaps is not solved, yet ...
otoh, there is also the `benchmarks' section. 

will try to incorporate your changes!

tim

-- 
tim_at_[hidden]
http://tim.klingt.org
Which is more musical, a truck passing by a factory or a truck passing
by a music school?
  John Cage