heap sort

heap-sort-imp.rb

class Array
  def left(i)
    2 * i + 1
  end

  def right(i)
    2 * i + 2
  end

  def heapify(i, heapsize)
    l = left(i)
    r = right(i)
    largest = i

    largest = l if l < heapsize && self[l] > self[largest]
    largest = r if r < heapsize && self[r] > self[largest]
    
    if largest != i
      self[i], self[largest] = self[largest], self[i]
      heapify(largest, heapsize)
    end
  end
  
  def build_max_heap
    nodes = self.length / 2 - 1
    nodes.downto(0) do |i|
      heapify(i, self.length)
    end
  end

  def heapsort
    build_max_heap
    start = self.length - 1
    start.downto 1 do |i|
      self[0], self[i] = self[i], self[0]
      heapify(0, i)
    end
    return self
  end
end