data_structures_lib/
heaps.rs1use crate::Error;
2
3pub struct Heap<T> {
5 data: Vec<T>,
6 less: Box<dyn Fn(&T, &T) -> bool>,
7}
8
9impl<T: Clone> Heap<T> {
10 pub fn new(less: impl Fn(&T, &T) -> bool + 'static) -> Self {
12 Self {
13 data: Vec::new(),
14 less: Box::new(less),
15 }
16 }
17
18 pub fn len(&self) -> usize {
20 self.data.len()
21 }
22
23 pub fn is_empty(&self) -> bool {
25 self.data.is_empty()
26 }
27
28 pub fn push(&mut self, value: T) {
30 self.data.push(value);
31 self.sift_up(self.data.len() - 1);
32 }
33
34 pub fn pop(&mut self) -> Result<T, Error> {
36 if self.is_empty() {
37 return Err(Error::Empty);
38 }
39 if self.data.len() == 1 {
40 return Ok(self.data.pop().unwrap());
41 }
42 let root = self.data[0].clone();
43 self.data[0] = self.data.pop().unwrap();
44 self.sift_down(0);
45 Ok(root)
46 }
47
48 pub fn peek(&self) -> Result<&T, Error> {
50 self.data.first().ok_or(Error::Empty)
51 }
52
53 pub fn to_vec(&self) -> Vec<T> {
55 self.data.clone()
56 }
57
58 fn sift_up(&mut self, mut index: usize) {
59 while index > 0 {
60 let parent = (index - 1) / 2;
61 if (self.less)(&self.data[index], &self.data[parent]) {
62 self.data.swap(index, parent);
63 index = parent;
64 } else {
65 break;
66 }
67 }
68 }
69
70 fn sift_down(&mut self, mut index: usize) {
71 let len = self.data.len();
72 loop {
73 let mut target = index;
74 let left = 2 * index + 1;
75 let right = 2 * index + 2;
76 if left < len && (self.less)(&self.data[left], &self.data[target]) {
77 target = left;
78 }
79 if right < len && (self.less)(&self.data[right], &self.data[target]) {
80 target = right;
81 }
82 if target == index {
83 break;
84 }
85 self.data.swap(index, target);
86 index = target;
87 }
88 }
89}
90
91pub struct MinHeap<T: Ord + Clone> {
93 inner: Heap<T>,
94}
95
96impl<T: Ord + Clone> MinHeap<T> {
97 pub fn new() -> Self {
99 Self {
100 inner: Heap::new(|a, b| a < b),
101 }
102 }
103
104 pub fn len(&self) -> usize {
106 self.inner.len()
107 }
108
109 pub fn is_empty(&self) -> bool {
111 self.inner.is_empty()
112 }
113
114 pub fn push(&mut self, value: T) {
116 self.inner.push(value);
117 }
118
119 pub fn pop(&mut self) -> Result<T, Error> {
121 self.inner.pop()
122 }
123
124 pub fn peek(&self) -> Result<&T, Error> {
126 self.inner.peek()
127 }
128
129 pub fn to_vec(&self) -> Vec<T> {
131 self.inner.to_vec()
132 }
133}
134
135impl<T: Ord + Clone> Default for MinHeap<T> {
136 fn default() -> Self {
137 Self::new()
138 }
139}
140
141pub struct MaxHeap<T: Ord + Clone> {
143 inner: Heap<T>,
144}
145
146impl<T: Ord + Clone> MaxHeap<T> {
147 pub fn new() -> Self {
149 Self {
150 inner: Heap::new(|a, b| a > b),
151 }
152 }
153
154 pub fn len(&self) -> usize {
156 self.inner.len()
157 }
158
159 pub fn is_empty(&self) -> bool {
161 self.inner.is_empty()
162 }
163
164 pub fn push(&mut self, value: T) {
166 self.inner.push(value);
167 }
168
169 pub fn pop(&mut self) -> Result<T, Error> {
171 self.inner.pop()
172 }
173
174 pub fn peek(&self) -> Result<&T, Error> {
176 self.inner.peek()
177 }
178
179 pub fn to_vec(&self) -> Vec<T> {
181 self.inner.to_vec()
182 }
183}
184
185impl<T: Ord + Clone> Default for MaxHeap<T> {
186 fn default() -> Self {
187 Self::new()
188 }
189}