簡易 PQueue

バイナリヒープの優先度付きキュー

使い方

pq = PQueue.new
%w/1 12 123 abcd abc/.each do |w|
  pq.enq(w,w.size) # 優先度を指定して追加する。#enq(value, priority)
end
puts pq.deq until pq.empty? # #deqでpriorityの小さいもの取り出せる

1
12
abc
123
abcd

class PQueue
  Node = Struct.new(:value, :priority)
  def initialize
    @heap = []
  end
  def size; @heap.size; end
  def empty?; @heap.empty?; end
  def peek; empty? ? nil : @heap[0].value; end
  def enq(value, priority)
    el = Node.new(value, priority)
    j = @heap.size
    @heap << nil
    while j > 0
      up = (j - 1) / 2
      break if @heap[up].priority < el.priority
      @heap[j] = @heap[up]
      j = up
    end
    @heap[j] = el
    self
  end
  def deq
    return nil if empty?
    return @heap.shift.value if size == 1
    
    ret = @heap[0]
    @heap[0] = nil
    el = @heap.pop
    
    i = 0
    while 2 * i + 1 < @heap.size
      l = 2 * i + 1
      r = 2 * i + 2
      j = (r == @heap.size || @heap[l].priority <= @heap[r].priority) ? l : r
      break if el.priority <= @heap[j].priority
      @heap[i] = @heap[j]
      i = j
    end
    @heap[i] = el
    return ret.value
  end
end