優先度付き待ち行列の実装
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ページを参考にさせていただきました。
優先度付き待ち行列