algo_rs/data_structure/heap/
binary_heap.rs

1use crate::data_structure::heap::{Heap, HeapFn};
2
3pub struct BinaryHeap<T> {
4    cmp: HeapFn<T>,
5    inner: Vec<T>,
6}
7
8impl<T> BinaryHeap<T> {
9    pub fn new(cmp: HeapFn<T>) -> Self {
10        Self {
11            cmp,
12            inner: Vec::<T>::new(),
13        }
14    }
15
16    pub fn with_capacity(cmp: HeapFn<T>, size: usize) -> Self {
17        Self {
18            cmp,
19            inner: Vec::<T>::with_capacity(size),
20        }
21    }
22
23    fn sift_down(&mut self) {
24        let size = self.inner.len();
25        let mut current = 0usize;
26        let mut running = true;
27
28        while running {
29            let left = current * 2 + 1;
30            let right = current * 2 + 2;
31            running = false;
32            if right < size && (self.cmp)(&self.inner[left], &self.inner[right]) {
33                if (self.cmp)(&self.inner[current], &self.inner[right]) {
34                    self.inner.swap(current, right);
35                    current = right;
36                    running = true;
37                }
38            } else if left < size {
39                if (self.cmp)(&self.inner[current], &self.inner[left]) {
40                    self.inner.swap(current, left);
41                    current = left;
42                    running = true;
43                }
44            }
45        }
46    }
47
48    fn sift_up(&mut self) {
49        let mut current = self.inner.len() - 1;
50
51        while current > 0 {
52            let parent = (current - 1) / 2;
53            if (self.cmp)(&self.inner[parent], &self.inner[current]) {
54                self.inner.swap(parent, current);
55            } else {
56                break;
57            }
58
59            current = parent;
60        }
61    }
62}
63
64impl<T> Heap<T> for BinaryHeap<T> {
65    fn push(&mut self, item: T) {
66        self.inner.push(item);
67        self.sift_up();
68    }
69
70    fn pop(&mut self) -> Option<T> {
71        if self.inner.is_empty() {
72            return None;
73        }
74
75        let last = self.inner.len() - 1;
76        self.inner.swap(0, last);
77        let result = self.inner.pop();
78        self.sift_down();
79        result
80    }
81
82    fn is_empty(&self) -> bool {
83        self.inner.is_empty()
84    }
85
86    fn peek(&self) -> Option<&T> {
87        return self.inner.first();
88    }
89}
90
91#[cfg(test)]
92mod tests {
93    use crate::data_structure::heap::binary_heap::BinaryHeap;
94    use crate::data_structure::heap::min_binary_heap::MinBinaryHeap;
95    use crate::data_structure::heap::Heap;
96    use std::collections;
97    extern crate test;
98    use test::Bencher;
99
100    #[test]
101    fn test_push_pop() {
102        let mut heap = BinaryHeap::new(|left, right| -> bool { left > right });
103        heap.push(3);
104        heap.push(2);
105        heap.push(1);
106        assert_eq!(Some(1), heap.pop());
107        assert_eq!(Some(2), heap.pop());
108        assert_eq!(Some(3), heap.pop());
109        assert_eq!(None, heap.pop());
110    }
111
112    #[test]
113    fn test_is_empty() {
114        let mut heap = BinaryHeap::new(|left, right| -> bool { left < right });
115        assert_eq!(true, heap.is_empty());
116        heap.push(3);
117        assert_eq!(false, heap.is_empty());
118        heap.pop();
119        assert_eq!(true, heap.is_empty());
120    }
121
122    #[test]
123    fn test_peek() {
124        let mut heap = BinaryHeap::new(|left, right| -> bool { left < right });
125        assert_eq!(None, heap.peek());
126        heap.push(3);
127        assert_eq!(Some(&3), heap.peek());
128        heap.pop();
129        assert_eq!(None, heap.peek());
130    }
131
132    #[bench]
133    fn bench_binary_heap_push_pop(b: &mut Bencher) {
134        b.iter(|| {
135            let mut heap = BinaryHeap::with_capacity(|left, right| -> bool { left < right }, 10000);
136            for i in 1..10000 {
137                heap.push(i)
138            }
139
140            for _ in 1..10000 {
141                heap.pop();
142            }
143        });
144    }
145
146    #[bench]
147    fn bench_min_binary_heap_push_pop(b: &mut Bencher) {
148        b.iter(|| {
149            let mut heap = MinBinaryHeap::with_capacity(10000);
150            for i in 1..10000 {
151                heap.push(i)
152            }
153
154            for _ in 1..10000 {
155                heap.pop();
156            }
157        });
158    }
159
160    #[bench]
161    fn bench_std_binary_heap_push_pop(b: &mut Bencher) {
162        b.iter(|| {
163            let mut heap = collections::BinaryHeap::with_capacity(10000);
164            for i in 1..10000 {
165                heap.push(i)
166            }
167
168            for _ in 1..10000 {
169                heap.pop();
170            }
171        });
172    }
173}
algo_rs/data_structure/heap/binary_heap.rs

algo_rs/data_structure/heap/
binary_heap.rs
