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

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