Skip to content

Instantly share code, notes, and snippets.

@bhelx

bhelx/pq.rb

Created Jul 23, 2012
Embed
What would you like to do?
Priority Queue with re assignable priorities
class PQueue
def initialize
@q = {}
end
def push(object, priority)
values = @q[priority] ||= []
values.push object
sync
object
end
def delete(object)
@q.each_pair do |p, vals|
return p if vals.delete(object)
end
end
def next
p = top_priority
p.last if p.any?
end
def pop
nxt = self.next
return unless nxt
p = delete nxt
zero_out p
sync
nxt
end
def alter_priority(object, diff)
@q.each_pair do |p, vals|
if vals.delete object
push(object, p + diff)
zero_out p
return object
end
end
end
private
def sync
@sorted_keys = @q.keys.sort
end
def top_priority
@q[@sorted_keys.last] || []
end
def zero_out(p)
@q.delete(p) if @q[p].empty?
end
end
pq = PQueue.new
pq.push '1', 1
pq.push '11', 1
pq.push '2', 2
pq.next #=> '2'
pq.alter_priority('11', 2) # bump priority up to 3 [1 +2]
pq.next #=> '11'
pq.pop #=> '11'
pq.pop #=> '2'
pq.pop #=> '1'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment