graph_tools/
heap.rs

1pub fn sort_heap_indices(heap : &mut [usize], values : &[usize]) {
2    
3    for size in (1..heap.len()).rev() {
4        (heap[0], heap[size]) = (heap[size], heap[0]);
5        siftdown_indices(0, heap, values, size);
6    }
7}
8
9pub fn heapify_indices(heap : &mut[usize], values : &[usize]){
10    for idx in (0..heap.len()/2).rev() {
11        siftdown_indices(idx, heap, values, heap.len());
12    }
13}
14
15pub fn heap_push_indices(val: usize, heap : &mut[usize], values : &[usize]){
16    if values[heap[0]] < values[val] {
17        heap[0] = val;
18        siftdown_indices(0, heap, values, heap.len());
19    }
20}
21
22#[inline]
23fn siftdown_indices(idx: usize, heap: &mut[usize], values: &[usize], size : usize){
24    let mut idx = idx;
25    loop {
26        let left_idx = idx * 2 + 1;
27        let right_idx = left_idx + 1;
28
29        if left_idx >= size { break; }
30        else if right_idx >= size || values[heap[left_idx]] <= values[heap[right_idx]] {
31            if values[heap[left_idx]] < values[heap[idx]] {
32                (heap[idx], heap[left_idx]) = (heap[left_idx], heap[idx]);
33                idx = left_idx;
34            }
35            else { break; }
36        }
37        else {
38            if values[heap[right_idx]] < values[heap[idx]] {
39                (heap[idx], heap[right_idx]) = (heap[right_idx], heap[idx]);
40                idx = right_idx;
41            }
42            else { break; }
43        }
44    }
45}
46
47
48
49
50
51
52/* The code below has not been tested */
53
54pub fn heap_push(val: usize, heap : &mut[usize]){
55    if heap[0] < val{
56        heap[0] = val;
57        siftdown(0, heap);
58    }
59}
60
61pub fn heapify(heap : &mut[usize]){
62    let size = heap.len();
63    for idx in (0..size/2).rev() {
64        siftdown(idx, heap);
65    }
66}
67
68#[inline]
69fn siftdown(idx: usize, heap: &mut[usize]){
70    let size = heap.len();
71    let mut idx = idx;
72    loop {
73        let left_idx = idx * 2 + 1;
74        let right_idx = left_idx + 1;
75        let p = heap[idx];
76
77        if left_idx >= size { break; }
78        else if right_idx >= size || heap[left_idx] <= heap[right_idx] {
79            if heap[left_idx] < p {
80                heap[idx] = heap[left_idx];
81                heap[left_idx] = p;
82                idx = left_idx;
83            }
84            else { break; }
85        }
86        else {
87            if heap[right_idx] < p {
88                heap[idx] = heap[right_idx];
89                heap[right_idx] = p;
90                idx = right_idx;
91            }
92            else { break; }
93        }
94    }
95}
graph_tools/heap.rs

graph_tools/
heap.rs
