Rust Heap sort ported from Rosetta code Dart example

heap_sort.rs

fn heap_sort<T: Ord>(a: &mut [T]) {
    let count:uint = a.len();
    
    // first place 'a' in max-heap order
    heapify(a, count);
    
    let mut end = count - 1;
    while end > 0 {
        // swap the root (maximum value) of the heap with the
        // last element of the heap
        a.swap(0, end);
        
        // put the heap back in max-heap order
        sift_down(a, 0, end - 1);
        
        // decrement the size of the heap so that the previous
        // max value will stay in its proper place
        end -= 1;
    }
}

fn heapify<T: Ord>(a: &mut [T], count: uint) {
    // start is assigned the index in 'a' of the last parent node
    let mut start:int = (count - 2 / 2) as int; // binary heap
    
    while start >= 0 {
        // sift down the node at index 'start' to the proper place
        // such that all nodes below the 'start' index are in heap order
        sift_down(a, start as uint, count - 1);
        start -= 1;
    }
}


fn sift_down<T: Ord>(a: &mut [T], start: uint, end: uint) {
    // end represents the limit of how far down the heap to shift
    let mut root = start;
    
    // while the root has at least one child
    while (root*2 + 1) <= end { 
        // root*2+1 points to the left child
        let mut child:uint = root*2 + 1 as uint;
        
        // if the chile has a sibling and the child's value is less that its sibling's...
        if child + 1 <= end && a[child] < a[child + 1] {
            // .. then point to the right child instead
            child = child + 1;
        }
        
        // out of max-heap order
        if a[root] < a[child] {
            a.swap(root, child);
            // repeat to continue shifting down the child now
            root = child;
        } else {
            return;
        }
    }
}

fn main() {
    let mut arr = [1u,5,2,7,3,9,4,6,8];
    heap_sort(arr);
    println!("After sort: {}", arr.as_slice());
    
    let mut arr = [1u,2,3,4,5,6,7,8,9];
    heap_sort(arr);
    println!("After sort: {}", arr.as_slice());
    
    let mut arr = [9u,8,7,6,5,4,3,2,1];
    heap_sort(arr);
    println!("After sort: {}", arr.as_slice());
    
    // After sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    // After sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    // After sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]
}