Thoughts
This whole big-O-notation thing is actually a big deal. Just rewrote a program keeping it in mind and it's so much faster.
I went from
# O(n) node insert
# O(n) node removal
# O(1) lookup
# O(1) popping (removing and returning the lowest score)
to
# O(log(n)) node insert
# O(1) node removal
# O(1) lookup
# O(1) popping (removing and returning the lowest score)
and the program is so much faster. I can't even say it's 10x faster or anything because it's no comparison. Like it's infinitely faster for large enough n.
No here's how I can compare them: After running the slow version for 42.8 seconds it spent 42.1 seconds in node-insertion and processed 17,745 nodes. After running the fast version for 42.2 seconds it spent 4.795 seconds doing node insertion and processed 1,045,985 nodes.
So that's a 58x increase in the number of nodes processed. The current bottleneck is all the operations on the individual nodes.