Re: [boost] [gsoc] heap review

Subject: Re: [boost] [gsoc] heap review
From: Michel MORIN (mimomorin_at_[hidden])
Date: 2011-05-28 07:34:29

Hi Tim,

Thank you for your work on this useful library!
I'm definitely interested in it.

I have a question about the library.
Are there linear-time functions to construct a heap from unordered data?
AFAIK, at least for d-ary heaps, there exists a linear time construction
algorithm (often called `build_heap`). In STL, there is `make_heap`
function which has linear-time complexity. I think such construction
functions are useful in some applications.

And here are some comments on source codes and documentation:
* Use of double underscores
In heap/detail/tree_iterator.hpp, there are a few names that contain
double underscores. But such names are reserved by compilers and
should not be used.

* Naming of functions of `increase` and `decrease`
For min heap, the meaning of `increase` and `decrease` becomes ambiguous.
Would it be nice to use ordinary `up_heap` and `down_heap` or
something like that?

* Coding style of nullary function signature
In header files and documentation, nullary functions are written as
    return_type some_function(void)
It is more C++'ish to write them as
    return_type some_function()

* Readability of ampersands
In the documentation (heap/xxxx_mutable.html), ampersands ('&') are
used in the description of `update`, `increase` and `decrease`.
I think it would be better to write 'and' instead of '&', since they are
a bit ambiguous with reference symbols.

Regards,
Michel