• 1

• 35.2k
• 13
• 134
• 238

heap Heap sort in rustRust

• 477
• 2
• 9

The tests are taken from this answer on an insertion sort in rust question.

The algorithm is taken from Algorithms in a nutshell (2nd edition).

I'm not looking at crazy performance, the goal being to learn about basic algorithms and rust, but if there is something shockingly inefficient please let me know.

fn main() {}
fn heapify<T>(slice: &mut [T], idx: usize, max: usize)
 where T: Ord
{
 let mut largest = idx;
 let left = idx*2 + 1;
 let right = idx*2 + 2;
 if left < max && slice[left] > slice[largest] {
 largest = left;
 }
 if right < max && slice[right] > slice[largest] {
 largest = right;
 }
 if largest != idx {
 slice.swap(largest, idx);
 heapify(slice, largest, max);
 }
}
fn heap_sort<T>(slice: &mut [T])
 where T: Ord
{
 let len = slice.len();
 if len <= 1 {
 return;
 }
 for i in (0..len/2).rev() {
 heapify(slice, i, len);
 }
 for i in (1..len).rev() {
 slice.swap(0, i);
 heapify(slice, 0, i);
 }
}
#[macro_use]
extern crate quickcheck;
#[test]
fn test_heapify() {
 let mut values = [8, 11, 9, 2, 10, 16];
 heapify(&mut values, 2, 6);
 assert_eq!(values, [8, 11, 16, 2, 10, 9]);
 heapify(&mut values, 1, 6);
 assert_eq!(values, [8, 11, 16, 2, 10, 9]);
 heapify(&mut values, 0, 6);
 assert_eq!(values, [16, 11, 9, 2, 10, 8]);
}
#[test]
fn test_heap_sort_empty() {
 let mut values: [i32; 0] = [];
 heap_sort(&mut values);
 assert_eq!(values, [])
}
#[test]
fn test_heap_sort_one() {
 let mut values = [1];
 heap_sort(&mut values);
 assert_eq!(values, [1]);
}
#[test]
fn test_heap_multi() {
 let mut values = [9, 8, 7, 11, 10];
 heap_sort(&mut values);
 let values_expected: Vec<_> = (7..12).collect();
 assert_eq!(values_expected, values);
}
quickcheck! {
 fn test_heap_everything(xs: Vec<i32>) -> bool {
 // Macro doesn't allow `mut` in the `fn` declaration :-(
 let mut xs = xs;
 let mut expected_sorted = xs.clone();
 expected_sorted.sort();
 heap_sort(&mut xs);
 expected_sorted == xs
 }
}