Раздел «Язык Ruby».HashHeap:

Структура данных HashHeap

Это очередь с приоритетом (priority queue) и одновременно ассоциативный массив (Hash). Хранит пары (k,v).

Идеи для языка Ruby

class IndexedValueArray <Array
  def []=(i,v)
    unless v.respond_to?(:idx)
      class <<v
        attr_accessor :idx
      end
    end
    v.idx = i 
    super(i,v)
  end
end

class HeapItem
  attr_accessor :k,:v,:idx
  def initialize(k,v,idx=0)
    @k,@v,@idx = k,v,idx
  end
  def <(x) # by default priority queue extracts pair with max value
    self.v < x.v 
  end
end

class HeapItemValueMaxKeyMin < HeapItem
  def <(x)
    self.v < x.v || (self.v == x.v && self.k > x.k)
  end
end

class HeapItemKeyMin < HeapItem
  def <(x)
    self.k > x.k
  end
end

class HeapItemValueMin < HeapItem
  def <(x)
    self.v > x.v
  end
end

class Heap
  attr_accessor :size
  def initialize(default_v=nil, item_klass=HeapItem)
    @d = IndexedValueArray.new
    @item_klass = item_klass
    @d[0] = @item_klass.new(nil,nil)
    @h = {}
    @size = 0
    @default_v = default_v
  end
  
  def clear
    @d.clear
    @h.clear
    @size = 0
  end
  
  def inspect
    "<Heap { d = " + @d[1..@size].map{|i|  [i.k,i.v,i.idx]}.inspect + "\n" +
    "size = " + @size.to_s + "}>"
  end
  
  def empty?
    @size==0
  end
  
  def extract_max
    extract_by_idx(1)
  end
  
  def extract_by_key(k)
    if i = @h[k]
      extract_by_idx(i.idx)
    else
      nil
    end
  end

  alias :delete :extract_by_key
  
  def extract_by_idx(idx)
    if @size >= idx
      res = @d[idx]
      @d[idx] = @d[@size]
      @h.delete(res.k)
      @size -= 1
      check_down(idx) if idx <= @size
      check_up(idx)
      [res.k,res.v]
    else
      nil
    end
  end
  
  def max
    return nil if size == 0
    [@d[1].k,@d[1].v]
  end
  
  def []=(k,v)
    i = @h[k]
    if i
      i.v = v
      check_up(i.idx)
      check_down(i.idx)
    else
      i = @item_klass.new(k,v)
      @size += 1
      @d[@size] = i
      @h[k] = i
      check_up(@size)
    end
    v
  end
  
  def [](k)
    return @h[k].v if @h[k]
    @default_v
  end

  def update(k)
    if @h.has_key?(k)
      idx = @h[k].idx
      check_up(idx)
      check_down(idx)
    end
  end
  
  def check_up(c)
    p = c/2
    while p > 0
      if @d[p] < @d[c]
        @d[p],@d[c] = @d[c],@d[p] 
        p,c = p/2,p
      else
        break
      end
    end
  end
  
  def check_down(p)
    # STDERR.puts p
    c = 2*p
    while c <= @size
      c += 1 if c + 1 <= @size &&  @d[c] < @d[c+1]
      if @d[p] < @d[c]
        @d[p],@d[c] = @d[c],@d[p] 
        p,c = c,2*c
      else
        break
      end
    end
  end

  # for testing purposes
  def indexed?
    (1..@size).all? {|i| @d[i].idx==i}
  end
  
  # for testing purposes 
  # besides binary relation "<" could be not linear.
  def heap?
    (2..@size).all? {|i| @d[i] < @d[i/2]}
  end
end

# Testing Heap class
if $0 == __FILE__
  require 'test/unit'
  require 'random' # see Random Mixin http://acm.mipt.ru/twiki/bin/view/Ruby/RandomArrayMixin 
  class HeapTest <Test::Unit::TestCase
    def test1
      h = Heap.new(nil,HeapItemValueMin)
      h2 = Heap.new(nil,HeapItemKeyMin)
      z = {}
      (0..10).to_a.shuffle.each_with_index do |i,v|
        h[i]=v
        h2[i]=v
        z[i]=v
      end
      assert(h.heap?)
      assert(h.indexed?)
   
      
      (0..10).each do |i|
        k,v = h.extract_max
        assert(h.indexed?) if i%10==0
        assert_equal(i,v)
        assert_equal([k,v], [k, z[k]])
      end
      
      (0..10).each do |i|
        k,v = h2.extract_max
        assert_equal(i,k)
      end
    end
  end
end

Решение задачи "С. Радио" c контеста МФТИ 2007 (PROBLEM:130)

tm = Hash.new(-601)
scores = Heap.new(0, HeapItemValueMaxKeyMin)
(1..200002).each {|i| scores[i]=0}

while line=gets
  cmd = line.split
  case cmd.shift
  when 'VOTE'
    ip = cmd.shift
    track,score,time = cmd.map{|x| x.to_i}
    if tm[ip] + 600 <= time
      tm[ip] = time
      scores[track] += score
    end
    puts scores[track]
  when 'GET'
    t,s = scores.extract_max
    scores[t] = -1
    puts "#{t} #{s}"
  when 'EXIT'
    puts 'OK'
    exit(0)
  end
end

-- ArtemVoroztsov - 08 Oct 2007