添え字付き優先度付き待ち行列の実装
Rubyで添え字付き優先度付き待ち行列を実装します。
これは一般的にあるものではないかもしれませんが、
あれば便利なのではないかと思います。
任意の要素とその優先度の二つを要素として
優先度順に任意の要素を取り出すという待ち行列です。
これもHeapを利用しています。
class PriorityQueueIndexComponent def initialize @index = [] @pqueue = [] @heap = Heap.new() end def push(index,elem) @index << [index,elem] @heap.push(@pqueue,elem) end def pop return_elem = @index[0][0] pop_elem = @heap.pop(@pqueue) @index.each do |index,elem| if elem == pop_elem return_elem = index break end end @index.delete_if { |index,elem| return_elem == index} return return_elem end end
実行します。
pqueue = PriorityQueueIndexComponent.new() pqueue.push('a',20) pqueue.push('b',5) pqueue.push('c',15) pqueue.push('d',4) pqueue.push('e',15) pqueue.push('f',9) pqueue.push('g',10) pqueue.push('h',8) puts pqueue.pop() puts pqueue.pop() puts pqueue.pop() puts pqueue.pop() puts pqueue.pop() puts pqueue.pop()
実行結果です。
a
c
e
g
f
h
Complete(0)