I think that it would be nice to have a unit test just for the heap. It could be useful in the long run to ease and control better refactoring. Also, it would double up as a internal documentation on how the heap is supposed to be used (I believe that this is our second heap implementation in sklearn, we also have the finbonacci heap, used in the dijkstra algorithm).