round-robin heaps in Ruby

round_robin_heap.rb

require "pp"

class Tree
  def insert(value)
    BlueFork.new(value, Null, Null).merge(self)
  end

  def merge(other)
    other._merge(self)
  end
end

Null = Tree.new
def Null.empty?
  true
end
def Null.merge(other)
  other
end
def Null._merge(other)
  other
end

class Fork < Tree
  attr_reader :value, :left, :right

  def initialize(value, left, right)
    @value, @left, @right = value, left, right
  end

  def empty?
    false
  end

  def min_elem
    value
  end

  def delete_min
    merge(left, right)
  end

  def _merge(other)
    if min_elem <= other.min_elem 
      self.join(other)
    else
      other.join(self)
    end
  end
end

class BlueFork < Fork
  def join(other)
    RedFork.new(value, left.merge(other), right)
  end
end

class RedFork < Fork
  def join(other)
    BlueFork.new(value, left, right.merge(other))
  end
end

pp (1..7).inject(Null) { |x, y| x.insert(y) }