class Heap
  def initialize(&block)
    @ary = []
    @pred = block || -> (a,b) { a < b }
  end

  def <<(value)
    n = size

    # 最後に追加
    @ary[n] = value

    # 適切な場所まで押し上げる
    while n != 0
      if precede?(@ary[n], @ary[parent(n)])
        @ary[parent(n)], @ary[n] = @ary[n], @ary[parent(n)]
        n = parent(n)
      else
        break
      end
    end

    self
  end

  def parent(n)
    (n-1)/2
  end

  def child_l(n)
    2*n+1
  end

  def child_r(n)
    2*n+2
  end

  def pop
    retval = @ary[0]

    # ヒープを保つ
    n = 0

    # 最後の要素をルートに持ってくる
    @ary[n] = @ary[size-1]
    @ary.pop

    # 適切な場所まで押し下げる
    loop do
      if (child_l(n) < size && !precede?(@ary[n], @ary[child_l(n)])) ||
         (child_r(n) < size && !precede?(@ary[n], @ary[child_r(n)]))

        if child_r(n) >= size || precede?(@ary[child_l(n)], @ary[child_r(n)])
          # 左の子と入れ替える
          @ary[n], @ary[child_l(n)] = @ary[child_l(n)], @ary[n]
          n = child_l(n)
        else #
          # 右の子と入れ替える
          @ary[n], @ary[child_r(n)] = @ary[child_r(n)], @ary[n]
          n = child_r(n)
        end
      else
        break
      end
    end

    retval
  end

  def empty?
    @ary.empty?
  end

  def size
    @ary.size
  end

  def to_a
    @ary.dup
  end

  # ソート済みの配列を返す
  def sort
    tmp = @ary.dup
    return [].tap do |retval|
      retval << pop until empty?
      @ary = tmp
    end
  end

  private

  def precede?(a, b)
    @pred.(a, b)
  end
end

def test
  # 整数をソート
  h = Heap.new
  h << 1 << 2 << -1 << 5 << 3
  p h.sort

  # 文字列を長さでソート
  h = Heap.new { |a,b| a.size < b.size }
  h << 'hello' << 'world' << 'ls' << 'dir' << 'pecarecorder'
  p h.sort

  a = []
  h = Heap.new { |a,b| a < b }
  100.times { a << rand }
  a.each { |x| h <<  x }
  p h.sort
  p a.sort
  p h.sort == a.sort
end

test if __FILE__ == $0