Heap Sort

struct MaxHeap {
    data: Vec<i32>,
}
 
impl MaxHeap {
    fn new() -> Self {
        MaxHeap { data: Vec::new() }
    }
 
    fn push(&mut self, val: i32) {
        self.data.push(val);
        // Bubble the new element up until the heap property is restored.
        let mut i = self.data.len() - 1;
        while i > 0 {
            let parent = (i - 1) / 2;
            if self.data[i] > self.data[parent] {
                self.data.swap(i, parent);
                i = parent;
            } else {
                break;
            }
        }
    }
 
    fn pop(&mut self) -> Option<i32> {
        if self.data.is_empty() {
            return None;
        }
        let n = self.data.len();
        self.data.swap(0, n - 1);
        let max = self.data.pop();
        // Sift the new root down to restore the heap property.
        self.sift_down(0, self.data.len());
        max
    }
 
    fn sift_down(&mut self, mut i: usize, heap_size: usize) {
        loop {
            let left  = 2 * i + 1;
            let right = 2 * i + 2;
            let mut largest = i;
 
            if left < heap_size && self.data[left] > self.data[largest] {
                largest = left;
            }
            if right < heap_size && self.data[right] > self.data[largest] {
                largest = right;
            }
 
            if largest == i {
                break; // heap property satisfied
            }
            self.data.swap(i, largest);
            i = largest;
        }
    }
}
 
fn heap_sort_naive(arr: &[i32]) -> Vec<i32> {
    // Phase 1: insert every element — O(n log n) via repeated push.
    let mut heap = MaxHeap::new();
    for &x in arr {
        heap.push(x);
    }
 
    // Phase 2: pop all elements — they come out in descending order.
    let mut result = Vec::with_capacity(arr.len());
    while let Some(val) = heap.pop() {
        result.push(val);
    }
 
    // Reverse to get ascending order.
    result.reverse();
    result
}
 
fn main() {
    let data = vec![12, 11, 13, 5, 6, 7];
    let sorted = heap_sort_naive(&data);
    println!("{:?}", sorted); // [5, 6, 7, 11, 12, 13]
}

fn heap_sort(arr: &mut [i32]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }
 
    // Phase 1 — Build max-heap using Floyd's bottom-up algorithm.
    //
    // Leaves (indices n/2..n) are trivially valid heaps of size 1.
    // Work backwards from the last internal node (n/2 - 1) to the root,
    // sifting each node down. This is O(n) total, not O(n log n).
    for i in (0..n / 2).rev() {
        sift_down(arr, i, n);
    }
 
    // Phase 2 — Sort by repeatedly extracting the maximum.
    //
    // The maximum is always arr[0] (the heap root). Swap it with the last
    // element in the unsorted region, shrink the heap by 1, and sift the
    // new root down to restore the heap property.
    for heap_end in (1..n).rev() {
        arr.swap(0, heap_end);          // move max to its final position
        sift_down(arr, 0, heap_end);    // restore heap over arr[..heap_end]
    }
}
 
/// Sift node at index `i` downward within arr[..heap_size].
/// Swaps with the largest child until the max-heap property holds.
fn sift_down(arr: &mut [i32], mut i: usize, heap_size: usize) {
    loop {
        let left  = 2 * i + 1;
        let right = 2 * i + 2;
        let mut largest = i;
 
        if left  < heap_size && arr[left]  > arr[largest] { largest = left;  }
        if right < heap_size && arr[right] > arr[largest] { largest = right; }
 
        if largest == i {
            break; // subtree rooted at i satisfies max-heap property
        }
 
        arr.swap(i, largest);
        i = largest; // follow the swapped element down
    }
}
 
fn main() {
    let mut data = vec![12, 11, 13, 5, 6, 7];
    heap_sort(&mut data);
    println!("{:?}", data); // [5, 6, 7, 11, 12, 13]
 
    // Works correctly on edge cases.
    let mut empty: Vec<i32> = vec![];
    heap_sort(&mut empty);
 
    let mut one = vec![42];
    heap_sort(&mut one);
    assert_eq!(one, [42]);
 
    // All duplicates — heap property is maintained even when all values equal.
    let mut dups = vec![3i32; 1000];
    heap_sort(&mut dups);
    assert!(dups.iter().all(|&x| x == 3));
}