I finally released a polished up version of my priority queue extension.
A priority-queue is usefull for algorithms like "dijkstras shortest
path algorithm" that finds shortest paths in a graph.

The extension now includes a pure ruby and a c extension. The runtime
behaviour can be seen at

  http://ruby.brian-schroeder.de/priority-queue/

which happens to be the project homepage.

I also added a rubyforge project and packed up the extension using
setup.rb and as a gem, so you should be able to do:

  gem install PriorityQueue

and have it working. But that is not reality as only version 0.1.0 has
found its way into the gem lists. I have asked tom what I did wrong,
so please be patient.

I would be very interested in feedback from people testing the
extension under exotic systems like aix and windows that I do not have
available at home.

I hope this will be usefull,

Brian

# Links:

  http://ruby.brian-schroeder.de/priority-queue/
  http://rubyforge.org/projects/priority-queue/

# Usage:

## Use it like a hash
require 'priority_queue'

q = PriorityQueue.new
q["node1"] = 0
q["node2"] = 1
q.min #=> "node1"
q[q.min] #=> 0
q.min_value #=> 0

q["node2"] = -1
q.delete_min #=> "node2", 1
q["node2"] #= nil
q["node3"] = 1

q.delete("node3") #=> "node3", 1
q.delete("node2") #=> nil

## Dijkstras shortest path algorithm:
def dijkstra(start_node)
  # Nodes that may have neighbours wich can be relaxed further
  active = PriorityQueue.new
  # Best distances found so far
  distances = Hash.new { 1.0 / 0.0 }
  # Parent pointers describing shortest paths for all nodes
  parents = Hash.new

  # Initialize with start node
  active[start_node] = 0
  until active.empty?
    u, distance = active.delete_min
    distances[u] = distance
    d = distance + 1
    u.neighbours.each do | v |
      next unless d < distances[v] # we can't relax this one
      active[v] = distances[v] = d
      parents[v] = u
    end
  end
  parents
end

PS: The raa entry is not updated as I have forgotten my password. I
already asked the admins to reset it, so I hope this will reflect
correct information soon. On a sidenote, what became of the plans to
synchronize rubyforge entries to raa?

--
http://ruby.brian-schroeder.de/

http://rubyforge.org/tracker/index.php?func=detail&aid=196&group_id=5...

if/when they occur...

Yours,

I have not looked very deep into rbtree. Maybe it is possible to
implement a priority queue on top of rbtree. But generally it seems
inverse to a priority queue. It orders by key, while a priority queue
orders by priority (value in hash terms).

A priority queue offers another (not a real subset) set of functions
than an rbtree. The complexity of the operations available in both
datastructures differs.

From the rbtree homepage:

"... the complexity for insert, search and delete is O(log N) in
expected and worst case."

while the complexities for the interesting operations in this priority
queue implementation are

insert O(1)
delete O(1) average
delete_min O(log n) average
change priority O(1) average

These properties allow for example to create an O(m + n log n)
shortest path algorithm where m is the number of edges and n the
number of nodes in the graph.

So to summerize, theses datastructures are different and are usefull
for different algorithms.

best regards,

Brian
--
http://ruby.brian-schroeder.de/

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/133202

but, Brian, your implementation sounds like it is better suited to being
a priority queue. Also, I think you said there is a pure ruby as well as
extension version of it, which is useful in some situations. I will
check it out when I get a chance, and maybe do some benchmarks.

cheers,

Brian

--
http://ruby.brian-schroeder.de/