heap_sort.rs

fn heapify<T: PartialOrd>(v: &mut [T], i: usize) {
    let len = v.len();
    let mut j = i;
    let mut max = i;
    loop {
        let l = j * 2 + 1;
        let r = j * 2 + 2;
        if l < len && v[l] > v[max] {
            max = l;
        }
        if r < len && v[r] > v[max] {
            max = r;
        }
        if max == j {
            break;
        }
        v.swap(j, max);
        j = max;
    }
}

fn heap_sort<T: PartialOrd>(v: &mut [T]) {
    let len = v.len();
    for i in (0..(len - 1) / 2 + 1).rev() {
        heapify(v, i);
    }
    for i in (0..len).rev() {
        v.swap(0, i);
        heapify(&mut v[0..i], 0);
    }
}

fn main() {
    let mut v = [5, 1, 4, 2, 6, 3];
    heap_sort(&mut v);
    println!("{:?}", v);
}