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

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

Rubyで優先度付き待ち行列を実装します。
Heapを利用することで容易にできます。

class PriorityQueue

    def initialize
        @pqueue = []
        @heap = Heap.new()
    end
    
    def push(elem)
        @heap.push(@pqueue,elem)
    end
    
    def pop
        return @heap.pop(@pqueue)
    end

end

実行します。

pqueue = PriorityQueue.new()

pqueue.push(20)
pqueue.push(5)
pqueue.push(15)
pqueue.push(4)
pqueue.push(3)
pqueue.push(9)
pqueue.push(10)
pqueue.push(6)
puts pqueue.pop()
puts pqueue.pop()
puts pqueue.pop()
puts pqueue.pop()
puts pqueue.pop()
puts pqueue.pop()

実行結果です。

20
15
10
9
6
5
Complete(0)

下記のWebページを参考にさせていただきました。
優先度付き待ち行列