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

`Comparable`

.Sorted queue based off of a red-black tree for Ruby.

This comment has been removed by the author.

ReplyDelete