Function sorting_rs::heap_sort::heap_sort

pub fn heap_sort<T: PartialOrd>(input: &mut [T])

Sorts a slice in-place using Heap sort, Bottom-up heap sort, Weak heap sort. All kinds of slices can be sorted as long as they implement PartialOrd.

Heap sort is basically an improved version of selection sort. Where the selection is now done in logarithmic time instead of linear.

First it transforms the array into a max-heap and then swaps the first element with the last element of the array, effectively shrinking the heap. Then it must max heapify again since the swapped value is smaller than the original max value. This process is repeated until there is no heap left.

Bottom-up version is modified version of this algorithm with decreased number of comparisons require function call or complex logic, then bottom-up version of algorithm is more effective.

Weak-heap sort main aim is to minimize amount of comparisons between elements. Amount of comparisons is basically lowered down to nearly nlogn - n / ln2 + O(logn).

Examples

let mut vec = vec![5, 2, 7, 3, 9];
sorting_rs::heap_sort(&mut vec);
debug_assert_eq!(vec, &[2, 3, 5, 7, 9]);

let mut strings = vec!["rustc", "cargo", "rustup"];
sorting_rs::heap_sort(&mut strings);
assert_eq!(strings, &["cargo", "rustc", "rustup"]);

let mut vec = vec![5, 2, 7, 3, 9];
sorting_rs::heap_bottom_up_sort(&mut vec);
debug_assert_eq!(vec, &[2, 3, 5, 7, 9]);

let mut strings = vec!["rustc", "cargo", "rustup"];
sorting_rs::heap_bottom_up_sort(&mut strings);
assert_eq!(strings, &["cargo", "rustc", "rustup"]);

let mut vec = vec![5, 2, 7, 3, 9];
sorting_rs::weak_heap_sort(&mut vec);
debug_assert_eq!(vec, &[2, 3, 5, 7, 9]);

let mut strings = vec!["rustc", "cargo", "rustup"];
sorting_rs::weak_heap_sort(&mut strings);
assert_eq!(strings, &["cargo", "rustc", "rustup"]);