そのような目的に使うデータ構造としては、ヒープツリーや優先順位つきキューというものがあり、
Rubyには長らくこれが標準だというような実装がなかった。ので、自分で作るか、
既存のものをさがすかということになります。

以下、最近できたものなので、あるよ、という紹介しかできませんが、
depqという優先順位つきキューのgemがあります（あるはずです）。
ttp://blade.nagaokaut.ac.jp/cgi-bin/vframe.rb/ruby/ruby-dev/39248?39066-39441