dsa/data_structures/
heap.rs

1use std::cmp::Ord;
2
3/// A binary heap data structure that can be either a max-heap or a min-heap.
4///
5/// A heap is a specialized tree-based data structure that satisfies the 
6/// heap property. In a max-heap, for every node `i` other than the root, 
7/// the value of `i` is less than or equal to the value of its parent. 
8/// Similarly, in a min-heap, for every node `i` other than the root, 
9/// the value of `i` is greater than or equal to the value of its parent.
10///
11/// This implementation allows you to specify whether the heap is a max-heap
12/// or a min-heap when creating it.
13pub struct Heap<T> {
14    /// The values stored in the heap.
15    ///
16    /// This vector maintains the heap property, where the values are ordered
17    /// according to whether the heap is a max-heap or a min-heap.
18    pub values: Vec<T>,
19
20    /// Whether the heap is a max-heap or a min-heap.
21    ///
22    /// If `true`, the heap will be a max-heap; if `false`, the heap will
23    /// be a min-heap.
24    pub is_max_heap: bool,
25}
26impl<T: Ord> Heap<T> {
27    /// Creates a new empty heap.
28    ///
29    /// # Parameters
30    /// - `is_max_heap`: A boolean flag indicating whether the heap is a
31    ///   max-heap (`true`) or a min-heap (`false`).
32    ///
33    /// # Returns
34    /// A new `Heap` instance with no elements.
35    ///
36    /// # Example
37    /// ```
38    /// use dsa::data_structures::heap::Heap;
39    /// 
40    /// let heap: Heap<i32> = Heap::new(true);
41    /// assert_eq!(heap.is_max_heap, true);
42    /// ```
43    pub fn new(is_max_heap: bool) -> Self {
44        Heap {
45            values: Vec::new(),
46            is_max_heap,
47        }
48    }
49    
50    /// Inserts a new value into the heap
51    /// 
52    /// # Parameters
53    /// - `value`: The value to insert into the heap
54    /// 
55    /// # Examples
56    /// ```
57    /// use dsa::data_structures::heap::Heap;
58    /// 
59    /// let mut heap = Heap::new(true);
60    ///
61    /// heap.insert(3);
62    /// heap.insert(1);
63    /// heap.insert(2);
64    /// heap.build_heap();
65    /// 
66    /// assert_eq!(heap.values, vec![3, 1, 2]);
67    /// ```
68    pub fn insert(&mut self, value: T) {
69        self.values.push(value);
70        self.sift_up(self.values.len() - 1);
71    }
72    
73    /// Sifts up a value in the heap to maintain the heap property
74    /// 
75    /// # Parameters
76    /// - `index`: The position of the newly inserted element that needs
77    ///    to be moved up
78    fn sift_up(&mut self, index: usize) {
79        if index == 0 {
80            return;
81        }
82        let parent = (index - 1) / 2;
83        let compare_result = if self.is_max_heap {
84            self.values[index] > self.values[parent]
85        } else {
86            self.values[index] < self.values[parent]
87        };
88
89        if compare_result {
90            self.values.swap(index, parent);
91            self.sift_up(parent);
92        }
93    } 
94
95    /// Builds the heap from the current values.
96    ///
97    /// This method ensures that the values stored in the heap follow the
98    /// heap property. It works by repeatedly calling the `sift_down` function
99    /// on each non-leaf node, starting from the last non-leaf node and going
100    /// up to the root.
101    ///
102    /// # Example
103    /// ```
104    /// use dsa::data_structures::heap::Heap;
105    /// 
106    /// let mut heap = Heap::new(true);
107    ///
108    /// heap.insert(3);
109    /// heap.insert(1);
110    /// heap.insert(2);
111    /// heap.build_heap();
112    ///
113    /// assert_eq!(heap.values, vec![3, 1, 2]);
114    /// ```
115    pub fn build_heap(&mut self) {
116        let len = self.values.len();
117        for i in (0..len - 1).rev() {
118            self.sift_down(i, len);
119        }
120    }
121    
122    /// Sifts down a value in the heap to maintain the heap property.
123    ///
124    /// This function compares the current node with its children and
125    /// swaps it with the larger (or smaller) child, depending on whether
126    /// it's a max-heap or min-heap. The process is repeated recursively
127    /// until the heap property is restored.
128    ///
129    /// # Parameters
130    /// - `index`: The index of the current node that needs to be sifted down.
131    /// - `len`: The total length of the heap (used to avoid out-of-bounds errors).
132    pub fn sift_down(&mut self, index: usize, len: usize) {
133        let left_child = 2 * index + 1;
134        let right_child = 2 * index + 2;
135        let mut largest_or_smallest = index;
136
137        if left_child < len {
138            let compare_result = if self.is_max_heap {
139                self.values[left_child] > self.values[largest_or_smallest]
140            } else {
141                self.values[left_child] < self.values[largest_or_smallest]
142            };
143
144            if compare_result {
145                largest_or_smallest = left_child;
146            }
147        }
148        if right_child < len {
149            let compare_result = if self.is_max_heap {
150                self.values[right_child] > self.values[largest_or_smallest]
151            } else {
152                self.values[right_child] < self.values[largest_or_smallest]
153            };
154
155            if compare_result {
156                largest_or_smallest = right_child;
157            }
158        }
159
160        if largest_or_smallest != index {
161            self.values.swap(index, largest_or_smallest);
162            self.sift_down(largest_or_smallest, len);
163        }
164    }
165}
dsa/data_structures/heap.rs

dsa/data_structures/
heap.rs
