Priority Queue with re assignable priorities

pq.rb

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'