Heap Sort Algorithm in Rust

1. Introduction

HeapSort is an efficient comparison-based sorting algorithm that leverages the properties of a binary heap data structure. It divides its input into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region. The time complexity of HeapSort is O(n log n) for both the worst and average cases, which makes it highly efficient.

2. Implementation Steps

1. Convert the input array into a max heap (a complete binary tree where each node is greater than its children).

2. Swap the first element (maximum value) with the last element of the heap.

3. Reduce the size of the heap by one, ensuring the reduced heap satisfies the max heap property.

4. Repeat steps 2 and 3 until the size of the heap is one.

3. Implementation in Rust Programming

// Function to turn an array into a max-heap
fn heapify<T: Ord>(arr: &mut [T], n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let 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 {
        arr.swap(i, largest);
        heapify(arr, n, largest);
    }
}
fn heap_sort<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    // Build max heap
    for i in (0..n / 2).rev() {
        heapify(arr, n, i);
    }
    // Extract elements from the heap
    for i in (0..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}
fn main() {
    let mut numbers = [12, 11, 13, 5, 6, 7];
    heap_sort(&mut numbers);
    println!("{:?}", numbers);  // Prints: [5, 6, 7, 11, 12, 13]
}

Output:

[5, 6, 7, 11, 12, 13]

Explanation:

1. The function heapify is responsible for enforcing the max-heap property on the array. If the parent node's value is less than its children, they are swapped, and the function is recursively called on the affected subtree.

2. The heap_sort function first constructs a max-heap from the provided array using the heapify function. Then, it repeatedly swaps the root (maximum value) of the heap with the last unsorted element of the array, reducing the heap size by one and ensuring the reduced heap remains a max-heap.

3. Swapping elements is done using Rust's standard library swap function.

4. The main function initializes a sample array, sorts it using heap_sort, and then prints the sorted array.