heap datastruture

heapds.rb

class Heap

  def initialize arr, type=:min
    @heap = arr
    self.class.class_eval { alias_method "get#{type.to_s}", :getroot } 
    if type == :min
      @op = :<
    else
      @op = :>
    end
  end

  def heapify
    start = @heap.size - 1
    while start > 0 
      bubble_up start
      start -= 1
    end
    @heap
  end

  def insert elem
    @heap << elem
    bubble_up(@heap.size-1)
  end

  def getroot
    root = @heap[0]
    @heap[0] = @heap.last
    @heap.pop
    bubble_down
    root
  end

  private
  def bubble_up start_from 
    child = start_from
    parent = (child - 1)/2
    while (@heap[child].send(@op, @heap[parent])) && (child != 0)
      @heap[parent], @heap[child] = @heap[child],@heap[parent]
      child = parent
      parent = (child-1)/2
    end
  end
  
  private
  def bubble_down 
    parent = 0
    child1 = parent*2 + 1
    child2 = parent*2 + 2

    while ((child1 < @heap.size) && (child2 < @heap.size))

      if @heap[child1].send(@op, @heap[child2])
        unless @heap[parent].send(@op,@heap[child1]) 
          @heap[parent], @heap[child1] = @heap[child1],@heap[parent]
          parent = child1
        else
          break
        end
      else
        unless @heap[parent].send(@op,@heap[child2]) 
          @heap[parent], @heap[child2] = @heap[child2],@heap[parent]
          parent = child2
        else
          break
        end
      end

      child1 = parent*2 + 1
      child2 = parent*2 + 2
      
    end
  end
end

class MinHeap < Heap  
  def initialize arr
    super arr,:min
  end
end

class MaxHeap < Heap
  def initialize arr
    super arr, :max
  end
end