algo_rs/data_structure/heap/
min_binary_heap.rs

1use crate::data_structure::heap::Heap;
2
3pub struct MinBinaryHeap<T: PartialOrd> {
4    inner: Vec<T>,
5}
6
7impl<T: PartialOrd> MinBinaryHeap<T> {
8    pub fn new() -> Self {
9        Self {
10            inner: Vec::<T>::new(),
11        }
12    }
13
14    pub fn with_capacity(size: usize) -> Self {
15        Self {
16            inner: Vec::<T>::with_capacity(size),
17        }
18    }
19
20    fn sift_down(&mut self) {
21        let size = self.inner.len();
22        let mut current = 0usize;
23        let mut running = true;
24
25        while running {
26            let left = current * 2 + 1;
27            let right = current * 2 + 2;
28            running = false;
29            if right < size && self.inner[left].gt(&self.inner[right]) {
30                if self.inner[current].gt(&self.inner[right]) {
31                    self.inner.swap(current, right);
32                    current = right;
33                    running = true;
34                }
35            } else if left < size {
36                if self.inner[current].gt(&self.inner[left]) {
37                    self.inner.swap(current, left);
38                    current = left;
39                    running = true;
40                }
41            }
42        }
43    }
44
45    fn sift_up(&mut self) {
46        let mut current = self.inner.len() - 1;
47
48        while current > 0 {
49            let parent = (current - 1) / 2;
50            if self.inner[parent].gt(&self.inner[current]) {
51                self.inner.swap(parent, current);
52            } else {
53                break;
54            }
55
56            current = parent;
57        }
58    }
59}
60
61impl<T: PartialOrd> Heap<T> for MinBinaryHeap<T> {
62    fn push(&mut self, item: T) {
63        self.inner.push(item);
64        self.sift_up();
65    }
66
67    fn pop(&mut self) -> Option<T> {
68        if self.inner.is_empty() {
69            return None;
70        }
71
72        let last = self.inner.len() - 1;
73        self.inner.swap(0, last);
74        let result = self.inner.pop();
75        self.sift_down();
76        result
77    }
78
79    fn is_empty(&self) -> bool {
80        self.inner.is_empty()
81    }
82
83    fn peek(&self) -> Option<&T> {
84        return self.inner.first();
85    }
86}
87
88#[cfg(test)]
89mod tests {
90    use crate::data_structure::heap::min_binary_heap::MinBinaryHeap;
91    use crate::data_structure::heap::Heap;
92    extern crate test;
93
94    #[test]
95    fn test_push_pop() {
96        let mut heap = MinBinaryHeap::new();
97        heap.push(3);
98        heap.push(2);
99        heap.push(1);
100        assert_eq!(Some(1), heap.pop());
101        assert_eq!(Some(2), heap.pop());
102        assert_eq!(Some(3), heap.pop());
103        assert_eq!(None, heap.pop());
104    }
105
106    #[test]
107    fn test_is_empty() {
108        let mut heap = MinBinaryHeap::new();
109        assert_eq!(true, heap.is_empty());
110        heap.push(3);
111        assert_eq!(false, heap.is_empty());
112        heap.pop();
113        assert_eq!(true, heap.is_empty());
114    }
115
116    #[test]
117    fn test_peek() {
118        let mut heap = MinBinaryHeap::new();
119        assert_eq!(None, heap.peek());
120        heap.push(3);
121        assert_eq!(Some(&3), heap.peek());
122        heap.pop();
123        assert_eq!(None, heap.peek());
124    }
125}
algo_rs/data_structure/heap/min_binary_heap.rs

algo_rs/data_structure/heap/
min_binary_heap.rs
