max_heap_sorting_ruby.rb

#Authore: Shubham Mishra

def heap_sort(arr)
  n = arr.length

  # Build a binary heap from the array
  (n / 2 - 1).downto(0) do |i|
    heapify(arr, n, i)
  end

  # Extract elements from the heap one by one
  (n - 1).downto(1) do |i|
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)
  end

  arr
end

def heapify(arr, n, i)
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2

  # Find the largest among the root, left child, and right child
  if left < n && arr[left] > arr[largest]
    largest = left
  end

  if right < n && arr[right] > arr[largest]
    largest = right
  end

  # Swap and heapify if the root is not the largest
  if largest != i
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)
  end
end

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr)
puts sorted_arr.join(' ')