Heap Sort Algorithms in Swift

1. Introduction

Heap Sort is a comparison-based sorting algorithm that leverages the properties of a binary heap. It divides its input into a sorted and an unsorted region and iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

2. Implementation Steps

1. Transform the input array into a max heap, a specialized tree-based data structure that satisfies the heap property.

2. Swap the first element of the heap with the last item. The largest item is now in its correct position in the array.

3. Reduce the size of the heap by one element, and siftdown the root of the heap to its proper place.

4. Repeat step 2 until the size of the heap is one.

3. Implementation in Swift

// Helper function: swaps two elements in an array
func swap<T>(_ array: inout [T], _ index1: Int, _ index2: Int) {
    let temp = array[index1]
    array[index1] = array[index2]
    array[index2] = temp
}
// Helper function: ensures that the heap property is maintained
func maxHeapify<T: Comparable>(_ array: inout [T], _ index: Int, _ heapSize: Int) {
    let left = 2 * index + 1
    let right = 2 * index + 2
    var largest = index
    if left < heapSize && array[left] > array[largest] {
        largest = left
    }
    if right < heapSize && array[right] > array[largest] {
        largest = right
    }
    if largest != index {
        swap(&array, index, largest)
        maxHeapify(&array, largest, heapSize)
    }
}
func heapSort<T: Comparable>(_ array: inout [T]) {
    var heapSize = array.count
    // Build max heap
    for i in stride(from: array.count / 2 - 1, through: 0, by: -1) {
        maxHeapify(&array, i, heapSize)
    }
    // Extract elements from heap
    for i in stride(from: array.count - 1, to: 0, by: -1) {
        swap(&array, 0, i)
        heapSize -= 1
        maxHeapify(&array, 0, heapSize)
    }
}
// Example Usage
var numbers = [38, 27, 43, 3, 9, 82, 10]
heapSort(&numbers)

Output:

The sorted array will be: [3, 9, 10, 27, 38, 43, 82]

Explanation:

1. Heap Sort works by visualizing the elements of the array as a special kind of complete binary tree called a heap.

2. The heap is constructed using a mathematical concept where each parent node has a value greater than or equal to the values of its children. This property ensures that the root always has the largest value.

3. Once the array has been transformed into a max heap, the algorithm extracts the largest element (root of the heap), and swaps it with the last item in the array. This ensures that the largest element moves to its correct sorted position.

4. The heap's size is reduced by one, and the root is heapified again to ensure the heap property. This process repeats until the entire array is sorted.

5. The main advantage of Heap Sort is that it's consistent in its performance, having a worst-case time complexity of O(n log n).

The Heap Sort method is an efficient way to sort an array of items, and its understanding provides insight into advanced data structures and algorithms.