class Heap
  attr :val, :height, :left, :right

  def initialize(val, height, left=nil, right=nil)
    @val = val
    @height = height
    @left = left
    @right = right
  end

  def dump(off=0)
    printf "%*s%d\n", off*2, nil, @val
    @left.dump(off+2) if @left
    @right.dump(off+2) if @right
  end

  def pop
    if @left.nil?
      [@val, @right]
    elsif @right.nil?
      [@val, @left]
    else
      left = @left
      right = @right
      if left.val < right.val
        root, left = left.pop
      else
        root, right = right.pop
      end
      lh = left ? left.height : 0
      rh = right ? right.height : 0
      height = 1 + (lh > rh ? lh : rh)
      [@val, Heap.new(root, height, left, right)]
    end
  end

  def self.insert(heap, val)
    if heap == nil || heap.val > val
      h = heap ? heap.height : 0
      Heap.new(val, 1+h, heap)
    else
      toleft = heap.left.nil? ||
              (!heap.right.nil? && rand(2) == 1)
      root, ins = heap.val, val
      left = heap.left
      right = heap.right
      if toleft
        left = insert(left, ins)
      else
        right = insert(right, ins)
      end
      lh = left ? left.height : 0
      rh = right ? right.height : 0
      height = 1 + (lh > rh ? lh : rh)
      Heap.new(root, height, left, right)
    end
  end
end

hp = nil
10.times do |i|
  val = rand(1000000)
  hp = Heap.insert(hp, val)
end
p hp.height
hp.dump
while hp
  val, hp = hp.pop
  printf "%d, ", val
end
puts
#hp.dump