Regarding PrioQueue

So, it turns out that if I use Oracle Java in Windows instead of OpenJDK on Linux, the performance is very different:

 - #1 Skilgannon's Cache-hit KDTree [0.0419]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0451]
 - #3 Rednaxela's kd-tree (2nd gen) [0.0458]
 - #4 Voidious' Linear search [0.7056]

1. All of them perform much worse in OracleJava/Windows than it did on OpenJDK/Linux
2. The relative performance of things looks much more similar to what you saw, with only a small difference between my 3rd and 2nd gen tree, with your one performing better

java version "1.7.0_25"
Java(TM) SE Runtime Environment (build 1.7.0_25-b17)
Java HotSpot(TM) Client VM (build 23.25-b01, mixed mode, sharing)

Client JVM is not designed for heavy processing, like how the rumble is.