rust_heap/
lib.rs

1pub mod heap;
2
3pub use heap::{BoundedBinaryHeap, BoundedBinaryHeaper, heapify, verify_heap};
4
5#[cfg(test)]
6mod tests {
7    use heap::{BoundedBinaryHeap, BoundedBinaryHeaper, heapify, verify_heap};
8    #[test]
9    fn test_empty_heap() {
10        let h: BoundedBinaryHeap<i32> = BoundedBinaryHeap::new(3);
11        assert_eq!(h.capacity(), 3);
12        assert_eq!(h.len(), 0);
13        assert!(h.is_empty());
14    }
15
16    #[test]
17    fn test_heap() {
18        let mut h = BoundedBinaryHeap::new(3);
19        h.push(10);
20        h.push(9);
21        h.push(8);
22        h.push(7);
23        h.push(6);
24        h.push(5);
25        assert_eq!(h.len(), 3);
26        assert_eq!(h.capacity(), 3);
27        assert_eq!(*h.peek().unwrap(), 8);
28        assert_eq!(h.pop().unwrap(), 8);
29        assert_eq!(h.pop().unwrap(), 9);
30        assert_eq!(h.pop().unwrap(), 10);
31        assert_eq!(h.pop(), None);
32        assert!(h.is_empty());
33    }
34
35    #[test]
36    fn test_heap_heapify() {
37        let mut h = BoundedBinaryHeap::from(&[7,9,8]);
38        assert_eq!(h.capacity(), 3);
39        assert_eq!(h.len(), 3);
40        assert!(!h.is_empty());
41        h.push(10);
42        h.push(6);
43        h.push(5);
44        assert_eq!(h.len(), 3);
45        assert_eq!(h.capacity(), 3);
46        assert_eq!(*h.peek().unwrap(), 8);
47        assert_eq!(h.pop().unwrap(), 8);
48        assert_eq!(h.pop().unwrap(), 9);
49        assert_eq!(h.pop().unwrap(), 10);
50        assert_eq!(h.pop(), None);
51        assert!(h.is_empty());
52    }
53
54    #[test]
55    fn test_heap_heapify_with_capacity() {
56        let mut h = BoundedBinaryHeap::from_slice_with_capacity(&[7,9,8], 5);
57        assert_eq!(h.capacity(), 5);
58        assert_eq!(h.len(), 3);
59        assert!(!h.is_empty());
60        h.push(6);
61        h.push(5);
62        h.push(10);
63        assert_eq!(h.len(), 5);
64        assert_eq!(h.capacity(), 5);
65        assert_eq!(*h.peek().unwrap(), 6);
66        assert_eq!(h.pop().unwrap(), 6);
67        assert_eq!(h.pop().unwrap(), 7);
68        assert_eq!(h.pop().unwrap(), 8);
69        assert_eq!(h.pop().unwrap(), 9);
70        assert_eq!(h.pop().unwrap(), 10);
71        assert_eq!(h.pop(), None);
72        assert!(h.is_empty());
73    }
74
75    #[test]
76    fn test_heaper() {
77        let mut v=[10, 9, 8];
78        let mut h = BoundedBinaryHeaper::from(&mut v);
79        h.push(7);
80        h.push(6);
81        h.push(5);
82        assert_eq!(h.len(), 3);
83        assert_eq!(h.capacity(), 3);
84        assert_eq!(*h.peek().unwrap(), 8);
85        assert_eq!(*h.pop().unwrap(), 8);
86        assert_eq!(*h.pop().unwrap(), 9);
87        assert_eq!(*h.pop().unwrap(), 10);
88        assert_eq!(h.pop(), None);
89        assert!(h.is_empty());
90    }
91
92    #[test]
93    fn test_heapify() {
94        let mut v=[10, 12, 9, 8, 7, 6, 5, 11, 3];
95        heapify(&mut v);
96        assert_eq!(v[0], 3);
97        assert!(verify_heap(&v));
98    }
99
100}