basic-non recursive heapsort in Rust

main.rs

fn lchild(root: usize) -> usize {
    root * 2 + 1
}

fn rchild(root: usize) -> usize {
    root * 2 + 2
}

fn biggest_child<T: Ord>(slice: &mut [T], root: usize) -> Option<usize> {
    let lchild = lchild(root);
    let rchild = rchild(root);

    if lchild >= slice.len() {
        // no children, already a max heap
        None
    } else if rchild >= slice.len() {
        // one child only
        Some(lchild)
    } else if slice[lchild] > slice[rchild] {
        // two children, left child bigger
        Some(lchild)
    } else {
        // one child, right child bigger
        Some(rchild)
    }
}

fn percolate_down<T: Ord>(slice: &mut [T], mut root: usize) {
    while let Some(biggest_child) = biggest_child(slice, root) {
        if slice[root] >= slice[biggest_child] {
            return;
        }
    
        slice.swap(root, biggest_child);
        root = biggest_child
    }
}

fn build_heap<T: Ord>(slice: &mut [T]) {
    for i in (0..slice.len()).rev() {
        percolate_down(slice, i);
    }
}

fn pop_max<T: Ord>(slice: &mut [T]) {
    let last_index = slice.len() - 1;
    slice.swap(0, last_index);
    percolate_down(&mut slice[..last_index], 0);
}

fn sort_heap<T: Ord>(slice: &mut [T]) {
    let length = slice.len();
    for i in (0..length).rev() {
        pop_max(&mut slice[..i + 1])
    }
}

fn heapsort<T: Ord>(slice: &mut [T]) {
    build_heap(slice);
    sort_heap(slice);
}

fn main() {
    let mut array = [8, 2, 5, 1, 7, 4, 10, 3, 6, 9];
    heapsort(&mut array);
    println!("{:?}", array);
}