datastructures/
heapnode.rs

1/// Heap Data Structure
2///
3/// # Examples
4///
5/// ```
6/// use datastructures::heapnode::HeapNode;
7/// 
8/// fn compare(parent: &i32, child: &i32) -> bool {
9///     parent < child
10/// }
11///
12/// let mut heap = HeapNode::new(compare);
13/// heap.insert(3);
14/// heap.insert(5);
15/// heap.insert(1);
16/// let poll = heap.poll();
17/// assert_eq!(5, poll.unwrap());
18/// ```
19pub struct HeapNode<T: Copy, F>
20where F: Fn(&T, &T) -> bool
21{
22    items: Vec<T>,
23    pub size: usize,
24    out_of_order: F,
25}
26
27impl<T: Copy, F> HeapNode<T, F>
28where T: Copy, F: Fn(&T, &T) -> bool
29{
30    pub fn new(out_of_order: F) -> Self {
31        HeapNode { items: vec![], size: 0 , out_of_order }
32    }
33
34    pub fn left_child_index(parent_index: usize) -> usize {
35        parent_index * 2 + 1
36    }
37
38    pub fn right_child_index(parent_index: usize) -> usize {
39        parent_index * 2 + 2
40    }
41
42    pub fn parent_index(child_index: usize) -> usize {
43        (child_index - 1) / 2
44    }
45
46    fn has_left_child(&self, parent_index: usize) -> bool {
47        Self::left_child_index(parent_index) < self.size
48    }
49
50    fn has_right_child(&self, parent_index: usize) -> bool {
51        Self::right_child_index(parent_index) < self.size
52    }
53
54    fn has_parent(&self, index: usize) -> bool {
55        // Self::parent_index(index) >= 0
56        index != 0
57    }
58
59    fn left_child(&self, parent_index: usize) -> &T {
60        &self.items[Self::left_child_index(parent_index)]
61    }
62
63    fn right_child(&self, parent_index: usize) -> &T {
64        &self.items[Self::right_child_index(parent_index)]
65    }
66
67    fn parent(&self, index: usize) -> &T {
68        &self.items[Self::parent_index(index)]
69    }
70
71    fn swap(&mut self, index_one: usize, index_two: usize) {
72        let tmp = self.items[index_one];
73        self.items[index_one] = self.items[index_two];
74        self.items[index_two] = tmp;
75    }
76
77    pub fn peak(&self) -> Option<&T> {
78        if self.size == 0 {
79            return None
80        }
81        Some(&self.items[0])
82    }
83
84    pub fn insert(&mut self, item: T) {
85        self.items.push(item);
86        self.size += 1;
87        self.heapify_up();
88    }
89
90    pub fn poll(&mut self) -> Option<T> {
91        if self.size == 0 {
92            return None
93        } else if self.size == 1 {
94            self.size = 0;
95            return self.items.pop()
96        }
97        let peak = *self.peak()?;
98        match self.items.pop() {
99            Some(item) => self.items[0] = item,
100            _ => (),
101        }
102        self.size -= 1;
103        self.heapify_down();
104        Some(peak)
105    }
106
107    fn heapify_down(&mut self) {
108        let mut cursor = 0;
109        while self.has_left_child(cursor) {
110            let mut smaller_child_index = Self::left_child_index(cursor);
111            if self.has_right_child(cursor) && (self.out_of_order)(
112                &self.left_child(cursor),
113                &self.right_child(cursor)
114            ) {
115                smaller_child_index = Self::right_child_index(cursor);
116            }
117            if (self.out_of_order)(
118                &self.items[cursor],
119                &self.items[smaller_child_index]
120            ) {
121                self.swap(cursor, smaller_child_index);
122                cursor = smaller_child_index;
123            } else {
124                break;
125            }
126        }
127    }
128
129    fn heapify_up(&mut self) {
130        let mut cursor = self.size - 1;
131        while self.has_parent(cursor) && (self.out_of_order)(
132            &self.parent(cursor),
133            &self.items[cursor]
134        ) {
135            let tmp = Self::parent_index(cursor);
136            self.swap(cursor, tmp);
137            cursor = tmp;
138        }
139    }
140}
datastructures/heapnode.rs

datastructures/
heapnode.rs
