Heapsort in ruby

heapsort.rb

=begin
implement heapsort in rails

https://en.wikipedia.org/wiki/Heapsort

Big(O) complexity
Time complexity (Average, Best, Worest cases): O(n log(n))
Space complexity: O(1)

test example
random array
6, 5, 3, 1, 8, 7, 2, 4

sorted array
1, 2, 3, 4, 5, 6, 7, 8
=end

class HeapSort
  attr_accessor :ary

  def initialize(ary)
    @ary = ary
    @size = ary.size
  end

  # apply ascending sort to the array
  def sort
    heapify
    partitions
  end

  private

=begin
  iParent     = floor((i-1) / 2)
  iLeftChild  = 2*i + 1
  iRightChild = 2*i + 2

  if index < 2 then its parent index 0
  if index >= 2 of array
    finding its parent from left_child = ((i - 1) / 2).floor
    finding its parent from right_child = (i - 2) / 2).ceil
  end
=end
  def heapify
    1.upto(@size - 1).each do |idx|
      if ary[idx] > ary[find_parent_idx_from_idx(idx)]
        recursive_swap_bottom_up(idx)
      end
    end
  end

  # recursive swap from bottom up, and it change the array
  # to match the heap structure
  #
  # @params idx [Fixnum] index of array
  def recursive_swap_bottom_up(idx)
    return if idx == 0

    parent_idx = find_parent_idx_from_idx(idx)
    if idx > 0 && ary[idx] > ary[parent_idx]
      swap(idx, parent_idx)
      recursive_swap_bottom_up(parent_idx)
    else
      return
    end
  end

  # Swap value in ary with index idx1 and idx2
  #
  # @params [idx1]
  # @params [idx2]
  def swap(idx1, idx2)
    temp = ary[idx1]
    ary[idx1] = ary[idx2]
    ary[idx2] = temp
  end

  # Find the parent index fromt he child index
  #
  # @params idx [Fixnum] eithe left child index or right child index
  # @returns [Fixnum] Parent index
  def find_parent_idx_from_idx(idx)
    if idx < 2
      return 0
    end

    if idx % 2 == 0
      ((idx - 1.0) / 2).floor
    else
      ((idx - 2.0) / 2).ceil
    end
  end

  # partition methods

  # Moving max value to the right
  # and reheapify the array
  def partitions
    partition_div_idx = @size - 1
    idx = 0
    while(partition_div_idx > idx)
      swap(idx, partition_div_idx)

      recursive_swap_top_down(idx, partition_div_idx)

      partition_div_idx -= 1
    end
  end

  # Reheapify the array after removing the root
  #
  # @params idx [Fixnum] current index
  # @params end_idx [Fixnum] index that root moved to
  def recursive_swap_top_down(idx, end_idx)
    return if idx == end_idx - 1

    left_child_idx = 2 * idx + 1
    if left_child_idx < end_idx && ary[idx] < ary[left_child_idx]
      swap(idx, left_child_idx)
      recursive_swap_top_down(left_child_idx, end_idx)
    end

    right_child_idx = 2 * idx + 2
    if right_child_idx < end_idx && ary[idx] < ary[right_child_idx]
      swap(idx, right_child_idx)
      recursive_swap_top_down(right_child_idx, end_idx)
    end

    return
  end
end

# Testing
ary = [6, 5, 3, 1, 8, 7, 2, 4]

s = HeapSort.new ary
s.sort
print s.ary
puts