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. The same argument can probably be made for binomial heaps and fibonacci heaps. Andrew