Tim, Do you really need to parametrize the constant-time size property? C++11 requires constant time size for all containers. I think that this is also a reasonable requirement for Heaps. I'm not aware of any applications that use so many heaps that the extra 4-8 bytes required by a size parameter would make huge difference in memory usage. Also, for heaps that can be effectively implemented in terms of other containers, they should guarantee O(1) size. The stability issue relates to a previous discussion from a couple months ago (brought up by Cliff Green, http://article.gmane.org/gmane.comp.lib.boost.devel/219330). Cliff was concerned that the implementation of stability added overhead to the normally unstable heaps (i.e., an extra size_t, I think) from the implementation. I worry that the use of a policy parameter to specify stability will result in "accidental overhead" in cases where users don't fully understand the impact of their configuration choices. Would it be better (would it be possible?) to write stable_heap as a heap adaptor? I think that this approach (if possible) has two benefits. First it encapsulates the strategy for implementing stability. It also provides a single point of reference for describing the impact of using that configuration. Andrew