Subject: Re: [boost] [gsoc] boost.heap update
From: Roland Bock (rbock_at_[hidden])
Date: 2010-07-29 07:35:36
Tim Blechmann wrote:
> 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
> 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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk