読者です 読者をやめる 読者になる 読者になる

添え字付き優先度付き待ち行列の実装

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)