I finally managed to install ruby 1.8.2 on my system again and recreated the PriorityQueue-0.1.2.gem. So now you can install the priority queue directly from the rubyforge gem server.

Just type

gem install PriorityQueue

and use it.

require "priority_queue"
q = PriorityQueue.new
...

cheers,

Brian