My review also... - What is your evaluation of the design? The design of the library included a number of features that did not seem to be adequately motivated by requirements, especially the ability to iterate over the elements of a heap. It's not obvious that any applications require or would use this feature, nor what specific requirements that they may have of iteration (heap-order vs. tree-order iteration. I feel that the design (of individual data structures) focuses too heavily on policy-based design. I think that there are a number of parameters that should be "positional parameters" rather than optionally or arbitrarily specified, especially the Compare functions since they define a fundamental property of the heaps. Also, the b_heap and d_ary heap should also be parameterized over (dynamic random access?). The concept of Mergeable heaps (those supporting efficient merge operations), at the time of submission, was inadequately addressed. - What is your evaluation of the implementation? The implementation is adequate and appears correct (based on inspection and performance comparisons). I think that the definition of heap equality and order may be strict to the point of inefficient. I think it should still be sufficient to define these operations in terms of object structure rather than the sequence of values produced. - What is your evaluation of the documentation? I think that the documentation could be substantially improved. It should start with an introduction of a basic Heap concept and describe the operations push, pop, top, size, and empty. This should be followed by a table of implementations and their runtime complexity for different operations. I feel that the documentation needs to explicitly present the concepts (as in heap_concepts.hpp) defined in the library. Also, it would be a good idea to tie the documentation into previously specified concepts in boost/concept_check.hpp. That would simplify the description of heaps as EqualityComparable and LessThanComparable, and also Container (for iterators, size and empty). The discussion of Mutability needs to be greatly enhanced. It isn't sufficient to simply show the interfaces for acquiring and updating handles. A Mutable Heap is really part of a larger data structure that incorporates a mapping between heaped objects and their handles. You can't really talk about real applications of Mutable Heaps without this mapping. This should be given much more attention in the description. I also would have liked to have seen a little more historical perspective in the introduction. Why was the library written? What libraries motivated the current design? - What is your evaluation of the potential usefulness of the library? As a collection of basic data structures, the library is potentially very useful. Not all data structures in the library are equally useful (binomial heap is largely obsolete), but they are still useful to others understand their design and implementation. - Did you try to use the library? With what compiler? Did you have any problems? Earlier versions of the library with GCC 4.5. I did not have any problems that I recall. I did not try to build a performance comparison as other reviewers did. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I spent a good amount of time inspecting the source code and documentation. - Are you knowledgeable about the problem domain? Yes. - Do you think the library should be accepted as a Boost library? Not in its current state. I feel that the library is over-designed and needs to be simplified. The problem is not that the author did not produce a viable design and implementation of a heap library. I think he did just that, and with some cleanups to the documentation and minor reworking of some implementation, this is a fine library. The problem is that library is comprised of a collection of fundamental data structures, some of which have been known for 30 or 40 years (if not more). This fact makes acceptance of such a library much harder than a lesser known or new domain. We all know about data structures and algorithms (and know them pretty well), and we all know what these data structures and how they work (or can figure it out). An ideal library of these data structures would perfectly match our expectations, whatever those may be. Any deviation from the ideal would be questionable, and that seems to be how the review played out. Conceptually, the notions of Mergeability and Mutability are not as crisply defined as I would have hoped. While it's possible to merge all heaps, only some are efficiently (i.e., O(lg n)) mergeable. I think that the approach to Mutability is well-conceived, but not particularly well communicated. It took me some time before I figured out its usage and implications. I'm still not convinced that Stability is an essential requirement, or that the library's approach to the solution is adequate. I would have preferred the library not attempt provide such a feature. The same could be said for iterators. Another issue is the absence of comparison with the BGL heaps. What benefits do we get from using your library? What benefits might we get from the BGL heaps? What are the real performance comparisons? Despite the fact that I am voting for not including the library, I see a great deal of value in its continued development and refinement and would encourage Tim to continue working towards an accepted Heap library for Boost. Andrew