One of the data structures required for implementing Dijkstra's algo is a priority queue. A strict priority queue won't quite work for me, as that requires numeric values for the priority, which I don't have. Instead I've defined a compare function for my nodes and want the queue to simply be sorted based on that.
Sadly Ruby doesn't have any built-in data structures for this. Arrays can be sorted and I could use that, but it would be incredibly inefficient as I would have to re-sort before every pop.
Thanks to the suggestion of jspcal on stackoverflow I found a couple libraries that implement sorted trees (Red-Black trees to be specific). Building a sorted queue on top of this was fairly easy.
Here's what I have so far. Eventually this will be checked into my github repository for ES, but for now I've posted the class as a gist, embedded below for convenience (I think I might have to switch to gists for all code embedding in my blog):
The only requirement for using the sorted queue is that the objects are
Sorted queue based off of a red-black tree for Ruby.