[ruby] Priority Queueの実装

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はどうですか。

タイトルとURLをコピーしました