algorithms_rs/heap.rs
1use alloc::vec::Vec;
2use core::fmt::{Debug, Display};
3
4fn parent(i: usize) -> usize {
5 i / 2
6}
7
8fn left(i: usize) -> usize {
9 ((i + 1) << 1) - 1
10}
11
12fn right(i: usize) -> usize {
13 (i + 1) << 1
14}
15
16/// Heap
17#[derive(Debug)]
18pub struct Heap<T> {
19 /// heap data
20 data: Vec<T>,
21 /// heap size
22 size: usize,
23}
24
25impl<T: Clone + PartialOrd + Default + Display + Debug> Default for Heap<T> {
26 fn default() -> Self {
27 Self::new()
28 }
29}
30
31impl<T: Clone + PartialOrd + Default + Display + Debug> Heap<T> {
32 /// Creating a empty heap
33 ///
34 /// ```rust
35 /// use algorithms_rs::Heap;
36 ///
37 /// let empty_heap = Heap::<i32>::new();
38 ///
39 /// assert_eq!(empty_heap.is_empty(), true);
40 /// ```
41 pub fn new() -> Self {
42 Self {
43 data: vec![],
44 size: 0,
45 }
46 }
47
48 /// Creating a heap from an array
49 ///
50 /// ```rust
51 /// use algorithms_rs::Heap;
52 ///
53 /// let empty_heap = Heap::<i32>::from_vector(&vec![1]).unwrap();
54 ///
55 /// assert_eq!(empty_heap.is_empty(), true);
56 /// ```
57 pub fn from_vector(array: &[T]) -> anyhow::Result<Self> {
58 if array.is_empty() {
59 return Err(anyhow::anyhow!("Can't create a empty heap"));
60 }
61
62 Ok(Self {
63 data: array.into(),
64 size: array.len() - 1,
65 })
66 }
67
68 /// Length of the heap
69 pub fn len(&self) -> usize {
70 self.size
71 }
72
73 /// Determine if the heap is empty
74 pub fn is_empty(&self) -> bool {
75 self.len() == 0
76 }
77
78 /// Get the internal data of the heap
79 pub fn inner_vec(&self) -> &[T] {
80 &self.data
81 }
82
83 /// Big root heap adjustment Recursive algorithm implementation
84 pub fn max_heapify(&mut self, index: usize) {
85 // setting largest is index
86 let mut largest = index;
87 let left = left(index);
88 let right = right(index);
89
90 // if left > largest then larget = left
91 if left <= self.len() && self.data.get(largest) < self.data.get(left) {
92 largest = left;
93 }
94
95 // if right > largest then largest = right
96 if right <= self.len() && self.data.get(largest) < self.data.get(right) {
97 largest = right;
98 }
99
100 if largest != index {
101 // swap vector index , largest value
102 self.data.swap(index, largest);
103 // rec call max_heapify
104 self.max_heapify(largest);
105 }
106 }
107
108 /// Small root heap adjustment Recursive algorithm implementation
109 pub fn min_heapify(&mut self, index: usize) {
110 // setting min is index
111 let mut min = index;
112 let left = left(index);
113 let right = right(index);
114
115 // if min > left then min = left
116 if left <= self.len() && self.data.get(min) > self.data.get(left) {
117 min = left;
118 }
119
120 // if min > right then min = right
121 if right <= self.len() && self.data.get(min) > self.data.get(right) {
122 min = right;
123 }
124
125 if min != index {
126 // swap vector index, min value
127 self.data.swap(index, min);
128 // rec call min_heapify
129 self.min_heapify(min);
130 }
131 }
132
133 /// Small root heap upward adjustment Non-recursive algorithm implementation
134 pub fn min_sift_up(&mut self, index: usize) {
135 let mut cur_idx = index;
136 loop {
137 // if cur_idx is root idx will break
138 if cur_idx == 0 {
139 break;
140 }
141
142 // get parent index
143 let parent_idx = parent(cur_idx);
144
145 // when parent node <= child node will break
146 if self.data[parent_idx] <= self.data[cur_idx] {
147 break;
148 }
149
150 // swap parent node idx with child node idx
151 self.data.swap(parent_idx, cur_idx);
152
153 // now cur_idx is assign to it's parent idx
154 cur_idx = parent_idx;
155 }
156 }
157
158 /// Big root heap upward adjustment Non-recursive algorithm implementation
159 pub fn max_sift_up(&mut self, index: usize) {
160 let mut cur_idx = index;
161 loop {
162 // if cur_idx is root idx will break
163 if cur_idx == 0 {
164 break;
165 }
166
167 // get parent index
168 let parent_idx = parent(cur_idx);
169
170 // when child node <= parent node will break
171 if self.data[cur_idx] <= self.data[parent_idx] {
172 break;
173 }
174
175 // swap parent node idx with child node idx
176 self.data.swap(parent_idx, cur_idx);
177
178 // now cur_idx is assign to it's parent idx
179 cur_idx = parent_idx;
180 }
181 }
182
183 /// Small root heap downward adjustment Non-recursive algorithm implementation
184 pub fn min_sift_down(&mut self, heap_len: usize) {
185 let mut cur_idx = 0usize;
186 loop {
187 // get cur_idx has left child idx
188 let mut child_idx = 2 * cur_idx + 1;
189
190 if cur_idx > heap_len || child_idx > heap_len {
191 break;
192 }
193
194 // child is the left child of cur_idx
195 // find left child and right child lesser child
196 if child_idx + 1 < heap_len && self.data[child_idx + 1] < self.data[child_idx] {
197 // right_child_idx is the right child of cur_idx
198 child_idx += 1;
199 }
200
201 // child is the lesser child of cur_idx
202 // if child's parent (cur_idx) <= child will break
203 if self.data[cur_idx] <= self.data[child_idx] {
204 break;
205 }
206
207 // otherwise swap lesser child idx with cur_idx(parent idx)
208 self.data.swap(child_idx, cur_idx);
209
210 // assign cur_idx with lesser child idx
211 cur_idx = child_idx;
212 }
213 }
214
215 /// Big root heap downward adjustment Non-recursive algorithm implementation
216 pub fn max_sift_down(&mut self, heap_len: usize) {
217 let mut cur_idx = 0usize;
218 loop {
219 // get cur_idx has left child idx
220 let mut child_idx = 2 * cur_idx + 1;
221
222 if cur_idx > heap_len || child_idx > heap_len {
223 break;
224 }
225
226 // child is the left child of cur_idx
227 // find left child and right child bigger child
228 if child_idx + 1 < heap_len && self.data[child_idx + 1] > self.data[child_idx] {
229 child_idx += 1;
230 }
231
232 // child is the lesser child of cur_idx
233 // if child's parent (cur_idx) > child will break
234 if self.data[cur_idx] > self.data[child_idx] {
235 break;
236 }
237
238 // otherwise swap lesser child idx with cur_idx(parent idx)
239 self.data.swap(child_idx, cur_idx);
240
241 // assign cur_idx with lesser child idx
242 cur_idx = child_idx;
243 }
244 }
245
246 /// Constructing a big root heap by recursive adjustment algorithm of big root heap
247 pub fn build_max_heap_by_max_heapify(&mut self) {
248 for index in (0..(self.len() / 2)).rev() {
249 self.max_heapify(index);
250 }
251 }
252
253 /// Construction of large root heap by non-recursive adjustment algorithm of large root heap
254 ///
255 /// ```rust
256 /// use algorithms_rs::Heap;
257 ///
258 /// let mut max_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();
259 ///
260 /// max_heap.build_max_heap_by_shift_up();
261 ///
262 /// assert_eq!(max_heap.inner_vec().to_vec(), vec![5, 4, 2, 3, 1])
263 /// ```
264 pub fn build_max_heap_by_shift_up(&mut self) {
265 // for i = [2; n]
266 // invariant : heap(1, i - 1)
267 // max_sift_up(i)
268 // heap(1, i)
269 for index in (0..self.data.len()).rev() {
270 self.max_sift_up(index);
271 }
272 }
273
274 /// Constructing rootlet heap by recursive adjustment algorithm of rootlet heap
275 pub fn build_min_heap_by_min_heapify(&mut self) {
276 for index in (0..(self.len() / 2)).rev() {
277 self.min_heapify(index);
278 }
279 }
280
281 /// Construction of rootlet heap by non-recursive adjustment algorithm of rootlet heap
282 ///
283 /// ```rust
284 /// use algorithms_rs::Heap;
285 ///
286 /// let mut min_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();
287 ///
288 /// min_heap.build_min_heap_by_siftup();
289 ///
290 /// assert_eq!(min_heap.inner_vec().to_vec(), vec![1, 2, 3, 4, 5]);
291 /// ```
292 pub fn build_min_heap_by_siftup(&mut self) {
293 // for i = [2; n]
294 // invariant : heap(1, i - 1)
295 // min_sift_up(i)
296 // heap(1, i)
297 for index in 0..self.data.len() {
298 self.min_sift_up(index);
299 }
300 }
301
302 /// Ascending sort implementation based on recursive implementation of the big root heap
303 ///
304 /// ```rust
305 /// use algorithms_rs::Heap;
306 ///
307 /// let mut max_heap = Heap::from_vector(&vec![5, 3, 7, 9, 10, 23, 45, 23, 12, 23, 0, 12, 32]).unwrap();
308 ///
309 /// max_heap.heap_sort_by_max_heap();
310 ///
311 /// assert_eq!(
312 /// max_heap.inner_vec().to_vec(),
313 /// vec![0, 3, 5, 7, 9, 10, 12, 12, 23, 23, 23, 32, 45]
314 /// );
315 /// ```
316 pub fn heap_sort_by_max_heap(&mut self) {
317 self.build_max_heap_by_max_heapify();
318 for index in (1..self.data.len()).rev() {
319 self.data.swap(0, index);
320 self.size -= 1;
321 self.max_heapify(0);
322 }
323 }
324
325 /// Descending sort implementation based on recursive implementation of small root heap
326 ///
327 /// ```rust
328 /// use algorithms_rs::Heap;
329 ///
330 /// let mut min_heap = Heap::from_vector(&vec![3, 2, 1, 0, 23, 34, 56, 11, 230, 12]).unwrap();
331 ///
332 /// min_heap.heap_sort_by_min_heap();
333 ///
334 /// assert_eq!(min_heap.inner_vec().to_vec(), vec![230, 56, 34, 23, 12, 11, 3, 2, 1, 0]);
335 /// ```
336 pub fn heap_sort_by_min_heap(&mut self) {
337 self.build_min_heap_by_min_heapify();
338 for index in (1..self.data.len()).rev() {
339 self.data.swap(0, index);
340 self.size -= 1;
341 self.min_heapify(0);
342 }
343 }
344
345 /// Descending sort implementation based on non-recursive implementation of small root heap
346 ///
347 /// ```rust
348 /// use algorithms_rs::Heap;
349 ///
350 /// let mut min_heap =
351 /// Heap::from_vector(&vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14]).unwrap();
352 /// min_heap.dec_sort_with_min_sift();
353 /// assert_eq!(
354 /// min_heap.inner_vec().to_vec(),
355 /// vec![14, 13, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
356 /// );
357 /// ```
358 pub fn dec_sort_with_min_sift(&mut self) {
359 // for (i = n; i >= 2; i --)
360 // heap(1, i) && sorted(i + 1, n) && x[1..i] <= x[i+1..n]
361 // swap(1, i)
362 // heap(2, i - 1) && sorted(i, n) && x[1..i-1] <= x[i..n]
363 // sift_down(i - 1)
364 // heap(1, i - 1) && sorted(i, n) && x[1..i - 1] <= x[i..n]
365 // build Min Heap by min siftup
366 self.build_min_heap_by_siftup();
367 for idx in (1..self.data.len()).rev() {
368 self.data.swap(0, idx);
369 self.min_sift_down(idx - 1);
370 }
371 }
372
373 /// Non-recursive implementation of ascending sort based on large root heap
374 ///
375 /// ```rust
376 /// use algorithms_rs::Heap;
377 ///
378 /// let mut max_heap = Heap::from_vector(&vec![9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 0]).unwrap();
379 ///
380 /// max_heap.asc_sort_with_max_sift();
381 ///
382 /// assert_eq!(max_heap.inner_vec().to_vec(), vec![0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]);
383 /// ```
384 pub fn asc_sort_with_max_sift(&mut self) {
385 // for (i = n; i >= 2; i --)
386 // heap(1, i) && sorted(i + 1, n) && x[1..i] <= x[i+1..n]
387 // swap(1, i)
388 // heap(2, i - 1) && sorted(i, n) && x[1..i-1] <= x[i..n]
389 // sift_down(i - 1)
390 // heap(1, i - 1) && sorted(i, n) && x[1..i - 1] <= x[i..n]
391 // build Max heap by max shiftup
392 self.build_max_heap_by_shift_up();
393 for idx in (1..self.data.len()).rev() {
394 self.data.swap(0, idx);
395 self.max_sift_down(idx - 1);
396 }
397 }
398}
399
400#[cfg(test)]
401mod tests {
402 use super::*;
403
404 #[test]
405 fn test_replace() {
406 let mut vec_temp = vec![1, 2, 3];
407 vec_temp.swap(0, 1);
408 assert_eq!(vec_temp, vec![2, 1, 3]);
409 }
410
411 #[test]
412 fn test_build_max_heap() {
413 let mut max_heap =
414 Heap::from_vector(&[5, 3, 7, 9, 10, 23, 45, 23, 12, 23, 0, 12, 32]).unwrap();
415 max_heap.heap_sort_by_max_heap();
416 assert_eq!(
417 max_heap.data,
418 vec![0, 3, 5, 7, 9, 10, 12, 12, 23, 23, 23, 32, 45]
419 );
420 }
421
422 #[test]
423 fn test_build_min_heap() {
424 let mut min_heap = Heap::from_vector(&[3, 2, 1, 0, 23, 34, 56, 11, 230, 12]).unwrap();
425 min_heap.heap_sort_by_min_heap();
426 assert_eq!(min_heap.data, vec![230, 56, 34, 23, 12, 11, 3, 2, 1, 0]);
427 }
428
429 #[test]
430 fn test_siftup_min_heap() {
431 let mut min_heap = Heap::from_vector(&[3, 2, 1, 4, 5]).unwrap();
432 min_heap.build_min_heap_by_siftup();
433 assert_eq!(min_heap.data, vec![1, 2, 3, 4, 5]);
434 }
435
436 #[test]
437 fn test_siftup_max_heap() {
438 let mut max_heap = Heap::from_vector(&[3, 2, 1, 4, 5]).unwrap();
439 max_heap.build_max_heap_by_shift_up();
440 assert_eq!(max_heap.data, vec![5, 4, 2, 3, 1])
441 }
442
443 #[test]
444 fn test_siftup_dec_sort() {
445 let mut min_heap =
446 Heap::from_vector(&[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14]).unwrap();
447 min_heap.dec_sort_with_min_sift();
448 assert_eq!(
449 min_heap.data,
450 vec![14, 13, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
451 );
452 }
453
454 #[test]
455 fn test_siftup_asc_sort() {
456 let mut max_heap = Heap::from_vector(&[9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 0]).unwrap();
457 max_heap.asc_sort_with_max_sift();
458 assert_eq!(max_heap.data, vec![0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]);
459 }
460}