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

Subject: Re: [boost] [gsoc] boost.heap update
From: Roland Bock (rbock_at_[hidden])
Date: 2010-07-29 07:35:36

Tim Blechmann wrote:
> hi,
> 
> thanks for looking into it ...

:-)

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

If you have some comment like // DON'T DO THIS AT HOME
no harm would come from showing incorrect code, I guess.

BTW: Wouldn't it be possible to check whether or not increase/decrease
are used correctly (and throw an exception otherwise)?

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

One idea would be to have a table for complexities for each pair of type
and action (i.e. push, top, pop, merge, ...). If you have different
values (e.g. optimal, average, worst-case), name them all. Maybe also
describe what optimal/worst-case look like.

Another might be size, number of memory allocations per element, stuff
like that.

> otoh, there is also the `benchmarks' section. 

That's nice, btw

One more thing: Even if boost heaps are probably quite easy to use, I'd
add a small tutorial/examples section that shows some working code using
heaps and their features.

Regards,

Roland