Ruby Max Heap Sort Implemenation

heap_sort.rb

def heap_sort(array)
  n = array.length - 1

  # turn the array into a max heap
  # where parent nodes(first element of the array) is larger than all its children
  (n / 2).downto(0) do |i|      
    create_max_heap(array, i, n) 
  end

  while n > 0
    # we swap the root element(max value) with the last element
    array[0], array[n] = array[n], array[0]
    # then reduce the size of the heap by 1 
    # and heapify the root element again 
    # so that we have highest element at root.
    n -= 1
    create_max_heap(array, 0, n)
  end
  array
end

# create max heap 
def create_max_heap(array, parent, limit)
  # parent indicates where to start shifting and limit tells how far down the heap to shift.
  #store the largest item in the root node.
  root = array[parent]
  while (child = 2 * parent) <= limit do
    child += 1 if child < limit && array[child] < array[child + 1]
    break if root >= array[child]
    array[parent], parent = array[child], child
  end
  # we put the root element of the heap at the end of the array
  array[parent] = root
end