RubyにPriority Queueがないので、皆さん自作の実装を持っていると思う。
もちろん私も私のPriority Queueがあるので公開しますね。
Priority Queue???
そもそも、Priority Queueとはなんぞやって人はこの記事を見ていない気はするのだけど、文字数を稼ぐためにちょっと書いておく。
え?じゃあどんな人を想定してこの記事を書いているんだって?
そりゃ、「お、RubyのPriority Queueか。俺のPriority Queueと、おまえのPriority Queue、どっちのほうがエレガントなのか、見せてみろやああああ」っていうバトル脳な人を想定しているのよ。
さて、Priority Queue、ちょっと日本語にすると「優先度付きキュー」。
このキューに入れたデータは、高速にソートされ、昇順、もしくは降順で取り出すことができる。
たとえば、昇順の優先度付きキューでは次のような振る舞いをすることになる。
queue = PriorityQueue.new
queue.add(5)
queue.add(2)
queue.add(7)
queue.pop
# => 2
queue.pop
# => 5
queue.pop
# => 7
実装
この実装を2分ヒープで実装したので、クラス名はHeapにした(適当すぎん?)。
class Heap
attr_reader :size
def initialize
@heap = []
@size = 0
end
def add(n)
i = @size
while i > 0 do
parent_index = (i - 1) / 2
break if n >= @heap[parent_index]
@heap[i] = @heap[parent_index]
i = parent_index
end
@heap[i] = n
@size += 1
end
def pop
return if @size <= 0
min_n = @heap[0]
@size -= 1
n = @heap[@size]
i = 0
while i * 2 + 1 < @size do
child_index1 = i * 2 + 1
child_index2 = i * 2 + 2
if child_index2 < @size && @heap[child_index2] < @heap[child_index1]
child_index1 = child_index2
end
break if @heap[child_index1] >= n
@heap[i] = @heap[child_index1]
i = child_index1
end
@heap[i] = n
min_n
end
def min; @heap[0] end
def values; @heap.first(@size) end
def inspect; "Heap: #{values}" end
end
あなたのPriority Queueはどうですか。