Are any of the heaps in your heap library stable, in the sense that if two equivalent objects are put on the heap it is guaranteed that the first one put on the heap will be the first one retrieved? If not, a stable_heap template might be a good addition to your library.