Heap Sort Algorithm in Ruby

1. Introduction

Heap sort is a comparison-based sorting algorithm that leverages the properties of a binary heap data structure to sort an array of values. It's an in-place sorting method with O(n log n) time complexity for both the worst and average cases.

2. Implementation Steps

1. Build a max heap from the input data.

2. The largest item is stored at the root of the max heap. Replace it with the last item of the heap, reducing the size of the heap by 1.

3. Reconstruct the heap.

4. Repeat step 2 while the size of the heap is not one.

3. Implementation in Ruby Programming

def heapify(arr, n, i)
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2
  # Check if left child exists and is greater than the current largest
  largest = left if left < n && arr[left] > arr[largest]
  # Check if right child exists and is greater than the current largest
  largest = right if right < n && arr[right] > arr[largest]
  # Swap and continue heapifying if the root isn't the largest
  if largest != i
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)
  end
end
def heap_sort(arr)
  n = arr.length
  # Build the heap (rearrange the array)
  (n / 2 - 1).downto(0) do |i|
    heapify(arr, n, i)
  end
  # Extract elements one by one from the heap
  (n - 1).downto(1) do |i|
    arr[i], arr[0] = arr[0], arr[i]   # Swap current root with the end
    heapify(arr, i, 0)                # Call max heapify on the reduced heap
  end
end
# Client code
array = [12, 11, 13, 5, 6, 7]
puts "Original array: #{array}"
heap_sort(array)
puts "Sorted array: #{array}"

Output:

Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]

Explanation:

1. Heap sort uses a binary heap which is a special tree-based data structure that satisfies the heap property.

2. The algorithm starts by building a max heap so that the largest element is at the root.

3. It then moves the root (the largest element) to the end of the array and reduces the size of the heap by 1.

4. This process is repeated, always extracting the root to the end of the array and reheapifying the remaining elements until the entire array is sorted.