# 1. Introduction

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. Heap Sort takes advantage of the properties of heaps, and the fact that the maximum (or minimum) element is always found at the root of the heap.

# 2. Implementation Steps

1. Build a max heap (or min heap for sorting in ascending order) from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap, followed by reducing the size of the heap by one. Finally, heapify the root of the tree.

3. Repeat the above steps while the size of the heap is not one.

# 3. Implementation in Scala

```
object HeapSort {
def sort(arr: Array[Int]): Unit = {
val n = arr.length
// Build a max heap
for (i <- (n / 2) - 1 to 0 by -1) {
heapify(arr, n, i)
}
// One by one extract elements from the heap
for (i <- n - 1 to 1 by -1) {
// Move current root to end
val temp = arr(0)
arr(0) = arr(i)
arr(i) = temp
// Call max heapify on the reduced heap
heapify(arr, i, 0)
}
}
// Function to heapify a subtree rooted with node `i` which is
// an index in `arr`. `n` is the size of the heap
def heapify(arr: Array[Int], n: Int, i: Int): Unit = {
var largest = i
val left = 2 * i + 1
val right = 2 * i + 2
if (left < n && arr(left) > arr(largest)) largest = left
if (right < n && arr(right) > arr(largest)) largest = right
if (largest != i) {
val swap = arr(i)
arr(i) = arr(largest)
arr(largest) = swap
heapify(arr, n, largest)
}
}
}
// Client code to test the heap sort algorithm
val array = Array(12, 11, 13, 5, 6, 7)
HeapSort.sort(array)
println(array.mkString(", "))
```

### Output:

5, 6, 7, 11, 12, 13

### Explanation:

1. The *sort* function starts by building a max heap using the input array.

2. After building the max heap, the root (which contains the largest element) is swapped with the last item. The size of the heap is then reduced by one. This process ensures that the largest current item moves to its final sorted position.

3. The *heapify* function ensures that the subtree rooted with a given node maintains the heap property (parent nodes are greater than or equal to their children).

4. The *heapify* function is called recursively to ensure that the entire tree maintains the heap property after each swap.

5. The process of extracting the root and then calling *heapify* is repeated until the heap size becomes one.