Implementation of max-heap in Ruby

max-heap.rb

# O(n)
def heapify(arr)
  last_element_index = arr.count - 1
  idx = parent_index(last_element_index)
  while idx >= 0
    arr = fix(arr, idx)
    idx -= 1
  end
  arr
end

def fix(arr, idx)
  if leaf_node?(arr, idx)
    return arr
  end

  if satisfies_heap_property?(arr, idx)
    return arr
  end

  swap = bigger_child(arr, idx)

  arr[idx], arr[swap] = arr[swap], arr[idx]

  fix(arr, swap)
end

def bigger_child(arr, idx)
  if arr[right_child(idx)]
    if arr[right_child(idx)] > arr[left_child(idx)]
      right_child(idx)
    else
      left_child(idx)
    end
  else
    left_child(idx)
  end
end

def satisfies_heap_property?(arr, idx)
  if arr[right_child(idx)]
    arr[right_child(idx)] <= arr[idx] && arr[left_child(idx)] <= arr[idx]
  else
    arr[left_child(idx)] <= arr[idx]
  end
end

def leaf_node?(arr, idx)
  arr[right_child(idx)].nil? && arr[left_child(idx)].nil?
end

def right_child(idx)
  idx * 2 + 2
end

def left_child(idx)
  idx * 2 + 1
end

def parent_index(idx)
  ((idx - 1) / 2.0).floor
end

def insert(el, arr)
  arr << el
  percolate_up(arr)
end

def percolate_up(arr)
  idx = arr.count - 1
  while has_parent?(idx)

    swap = parent_index(idx)
    if arr[idx] > arr[swap]
      arr[swap], arr[idx] = arr[idx], arr[swap]
    end
    idx = parent_index(idx)
  end
  arr
end

def has_parent?(idx)
  ((idx - 1)/ 2).floor >= 0
end

# O(log n)
def delete_max(arr)
  swap = arr.count - 1
  arr[0], arr[swap] = arr[swap], arr[0]
  arr.pop
  fix(arr, 0)
end

# n elements * delete_max => O(n log n)
def heap_sort(arr)
  ret = []
  while arr.count > 0
    ret << arr[0]
    arr = delete_max(arr)
  end
  ret
end

arr = heapify([1,2,3,4,5,6,7,8,9,10])
puts arr.join(',')

arr = insert(11, arr)
puts arr.join(',')

puts "max element: #{arr[0]}"
arr = delete_max(arr)
puts arr.join(',')


puts "heap sorting: #{heap_sort(arr).join(',')}"