Skip to main content

data_structures_lib/
heaps.rs

1use crate::Error;
2
3/// A generic binary heap.
4pub struct Heap<T> {
5    data: Vec<T>,
6    less: Box<dyn Fn(&T, &T) -> bool>,
7}
8
9impl<T: Clone> Heap<T> {
10    /// Creates a new Heap with the given comparison function.
11    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    /// Returns the number of elements.
19    pub fn len(&self) -> usize {
20        self.data.len()
21    }
22
23    /// Returns true if the heap is empty.
24    pub fn is_empty(&self) -> bool {
25        self.data.is_empty()
26    }
27
28    /// Pushes a value.
29    pub fn push(&mut self, value: T) {
30        self.data.push(value);
31        self.sift_up(self.data.len() - 1);
32    }
33
34    /// Pops and returns the top value.
35    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    /// Returns the top value without removing it.
49    pub fn peek(&self) -> Result<&T, Error> {
50        self.data.first().ok_or(Error::Empty)
51    }
52
53    /// Returns a Vec of the heap's data.
54    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
91/// A min-heap for ordered types.
92pub struct MinHeap<T: Ord + Clone> {
93    inner: Heap<T>,
94}
95
96impl<T: Ord + Clone> MinHeap<T> {
97    /// Creates a new MinHeap.
98    pub fn new() -> Self {
99        Self {
100            inner: Heap::new(|a, b| a < b),
101        }
102    }
103
104    /// Returns the number of elements.
105    pub fn len(&self) -> usize {
106        self.inner.len()
107    }
108
109    /// Returns true if the heap is empty.
110    pub fn is_empty(&self) -> bool {
111        self.inner.is_empty()
112    }
113
114    /// Pushes a value.
115    pub fn push(&mut self, value: T) {
116        self.inner.push(value);
117    }
118
119    /// Pops and returns the minimum value.
120    pub fn pop(&mut self) -> Result<T, Error> {
121        self.inner.pop()
122    }
123
124    /// Returns the minimum value.
125    pub fn peek(&self) -> Result<&T, Error> {
126        self.inner.peek()
127    }
128
129    /// Returns a Vec of the heap's data.
130    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
141/// A max-heap for ordered types.
142pub struct MaxHeap<T: Ord + Clone> {
143    inner: Heap<T>,
144}
145
146impl<T: Ord + Clone> MaxHeap<T> {
147    /// Creates a new MaxHeap.
148    pub fn new() -> Self {
149        Self {
150            inner: Heap::new(|a, b| a > b),
151        }
152    }
153
154    /// Returns the number of elements.
155    pub fn len(&self) -> usize {
156        self.inner.len()
157    }
158
159    /// Returns true if the heap is empty.
160    pub fn is_empty(&self) -> bool {
161        self.inner.is_empty()
162    }
163
164    /// Pushes a value.
165    pub fn push(&mut self, value: T) {
166        self.inner.push(value);
167    }
168
169    /// Pops and returns the maximum value.
170    pub fn pop(&mut self) -> Result<T, Error> {
171        self.inner.pop()
172    }
173
174    /// Returns the maximum value.
175    pub fn peek(&self) -> Result<&T, Error> {
176        self.inner.peek()
177    }
178
179    /// Returns a Vec of the heap's data.
180    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}