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