Heap Sort Algorithm in Scala

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.