Tim, you're proposing this b-heap purely as a performance optimisation compared to the "traditional" heap, but we've not yet seen any cases where it is actually faster. If it can be faster we need to see some examples, and the documentation should qualify when it can be expected to be better. If it's not faster, it should be dropped.
I don't think removal would be the right solution, but it certainly shouldn't be recommended as a best choice. Part of what I like about this library is that it provides a framework for evaluating comparative heap performance. While it doesn't appear to perform as well now, it's possible that future architectures may be more amenable to b-heap implementations. If not, then Boost has an implementation that can be used to empirically demonstrate otherwise.
i read somewhere that binary heaps are usually the first and the last answer when choosing a heap data structure ... although they have an amortized complexity of O(log(n)) for most operations.
The same argument can probably be made for binomial heaps and fibonacci heaps.
binomial heaps implement most operations in O(log(n)) worst-case and are efficiently mergable ... fibonacci heaps are of interest, since the support `push' and `merge' in O(1) amortized complexity (at the cost of implementing some operations in O(n) worst- case complexity) so the selection of the best heap data structure is really dependent on: * the type (efficiency of std::swap and comparison like std::less) * the size of the problem (for small sizes you do not need to care about the amortized complexity so much) * is the program focussed on throughput or worst-case latency * the use case: different access patterns have different performance characteristics. so instead of telling the people to `use this', i prefer to give people a choice to select the best data structure for their applications tim