Interval Heap vs MinHeap

How about keeping a flag in your leaf node processing so that you only try pruning if you added a new item?

Just tried that. The pruning is still not paying off compared to the extra overhead of the IntervalHeap.

And how about if you just use the IntervalHeap, but don't try any pruning? I'm curious whether the pruning is slow, or the different heap.

I was thinking it was the different heap... but actually turns out the heaps are approximately the same performance, with the difference being the pruning:

 - #1 Rednaxela's kd-tree (3rd gen, Interval Heap) [0.0290]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0290]
 - #3 Rednaxela's kd-tree (3rd gen, Interval Heap, Prune When Points Added) [0.0293]
 - #4 Rednaxela's kd-tree (3rd gen, Interval Heap, Avoid Growing Heap When Possible) [0.0294]
 - #5 Skilgannon's Cache-hit KDTree [0.0296]

So the incremental difference from a larger heap is less than the cost of removing the points.