AOJ(ALDS)その2

AIZU ONLINE JUDGE: Programming Challenge
 

ALDS1_9_A Complete Binary Tree

#完全二分木
$<.gets
given = [nil] + $<.gets.split.map(&:to_i)
a = nil
 
given.drop(1).each_with_index do |key, i|
  j = i + 1
  str = "node #{j}: key = #{key}, "
  str += "parent key = #{a}, " if (a = given[j / 2])
  str += "left key = #{a}, "   if (a = given[j * 2])
  str += "right key = #{a}, "  if (a = given[j * 2 + 1])
  puts str
end

 

ALDS1_9_B Maximum Heap

#最大ヒープ
h = $<.gets.to_i
given = [nil] + $<.gets.split.map(&:to_i)
 
max_heapify = ->(i) {
  l, r = i * 2, i * 2 + 1
  largest = (l <= h and given[l] > given[i]) ? l : i
  largest = r if r <= h and given[r] > given[largest]
  unless largest == i
    given[i], given[largest] = given[largest], given[i]
    max_heapify.(largest)
  end
}
 
(h / 2).downto(1) {|i| max_heapify.(i)}
puts given.drop(1).map {|i| " #{i}"}.join

 

ALDS1_9_C Priority Queue

#優先度付きキュー
class MaxHeap
  def initialize
    @heap = [nil]
    @size = 0
  end
   
  def insert(key)
    @heap << key
    @size += 1
    up_heap(@size / 2)
  end
   
  def up_heap(i)
    return if i.zero?
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      up_heap(i / 2)
    end
  end
   
  def remove_root
    a = @heap[1]
    @heap[1] = @heap.pop
    @size -= 1
    down_heap(1)
    a
  end
   
  def down_heap(i)
    return if i > @size
    l, r = i * 2, i * 2 + 1
    largest = (l <= @size and @heap[l] > @heap[i]) ? l : i
    largest = r if r <= @size and @heap[r] > @heap[largest]
    unless largest == i
      @heap[i], @heap[largest] = @heap[largest], @heap[i]
      down_heap(largest)
    end
  end
end
 
 
h = MaxHeap.new
 
$<.readlines.map {|l| l.chomp.split}.each do |command|
  case command[0]
  when "insert" then h.insert(command[1].to_i)
  when "extract" then puts h.remove_root
  when "end" then break
  else raise "error"
  end
end

 

ALDS1_10_A Fibonacci Number

#フィボナッチ数列
fib = Enumerator.new do |y|
  a, b = 1, 1
  loop do
    y << a
    a, b = b, a + b
  end
end
 
puts fib.take($<.gets.to_i + 1).last