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}