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}