Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
m (→{{header|TI-83 BASIC}}: off topic) |
(→{{header|Rust}}: Added rust) |
||
Line 3,357:
irb(main):036:0> ary.heapsort
=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</pre>
=={{header|Rust}}==
{{trans|Python}}
This program allows the caller to specify an arbitrary function by which an order is determined.
<lang rust>use std::mem;
fn main() {
let mut v = vec![1,1,1,2,1,1,1];
heap_sort(&mut v, |x,y| x < y);
println!("{:?}", v);
}
fn heap_sort<T,F>(array: &mut [T], order: F)
where F: Fn(&T,&T) -> bool
{
let len = array.len();
// Create heap
for start in (0..len/2).rev() {
sift_down(array,&order,start,len-1)
}
for end in (1..len).rev() {
{
let (b,e) = array.split_at_mut(1);
mem::swap(&mut b[0], &mut e[end-1]);
}
sift_down(array,&order,0,end-1)
}
}
fn sift_down<T,F>(array: &mut [T], order: &F, start: usize, end: usize)
where F: Fn(&T,&T) -> bool
{
let mut root = start;
loop {
let mut child = root * 2 + 1;
if child > end { break; }
if child + 1 <= end && order(&array[child], &array[child + 1]) {
child += 1;
}
if order(&array[root], &array[child]) {
let (r,c) = array.split_at_mut(child);
mem::swap(&mut r[root], &mut c[0]);
root = child
} else {
break;
}
}
}</lang>
=={{header|Scala}}==
| |||