graph_collections/
priority_queue.rs

1use crate::MinHeap;
2
3/// A keyed priority queue that pops by **lowest priority first**.
4///
5/// Backed by [`MinHeap`] with `(P, T)` pairs. Because Rust's tuple ordering
6/// is lexicographic, storing `(priority, value)` gives us priority ordering
7/// for free.
8///
9/// # Use case
10///
11/// This is the queue Dijkstra's algorithm uses:
12/// push a `(node, cost)` pair and always pop the cheapest node next.
13///
14/// # Examples
15///
16/// ```
17/// use graph_collections::PriorityQueue;
18///
19/// let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
20///
21/// pq.push("low",    10);
22/// pq.push("high",    1);
23/// pq.push("medium",  5);
24///
25/// assert_eq!(pq.peek_priority(), Some(&1));
26///
27/// assert_eq!(pq.pop(), Some(("high",   1)));
28/// assert_eq!(pq.pop(), Some(("medium", 5)));
29/// assert_eq!(pq.pop(), Some(("low",   10)));
30/// assert!(pq.is_empty());
31/// ```
32#[derive(Debug, Clone)]
33pub struct PriorityQueue<T: Ord, P: Ord> {
34    /// Internally stores `(priority, value)` so [`MinHeap`]'s lexicographic
35    /// ordering promotes the smallest priority to the top.
36    heap: MinHeap<(P, T)>,
37}
38
39impl<T: Ord, P: Ord> Default for PriorityQueue<T, P> {
40    fn default() -> Self {
41        Self {
42            heap: MinHeap::new(),
43        }
44    }
45}
46
47impl<T: Ord, P: Ord> PriorityQueue<T, P> {
48    /// Creates a new, empty priority queue.
49    ///
50    /// # Examples
51    ///
52    /// ```
53    /// use graph_collections::PriorityQueue;
54    ///
55    /// let pq: PriorityQueue<&str, u32> = PriorityQueue::new();
56    /// assert!(pq.is_empty());
57    /// ```
58    pub fn new() -> Self {
59        Self::default()
60    }
61
62    /// Creates a new, empty priority queue with at least the given capacity
63    /// pre-allocated.
64    ///
65    /// # Examples
66    ///
67    /// ```
68    /// use graph_collections::PriorityQueue;
69    ///
70    /// let pq: PriorityQueue<u32, u32> = PriorityQueue::with_capacity(128);
71    /// assert!(pq.is_empty());
72    /// ```
73    pub fn with_capacity(capacity: usize) -> Self {
74        Self {
75            heap: MinHeap::with_capacity(capacity),
76        }
77    }
78}
79
80impl<T: Ord, P: Ord> PriorityQueue<T, P> {
81    /// Returns `true` if the queue contains no elements.
82    ///
83    /// # Examples
84    ///
85    /// ```
86    /// use graph_collections::PriorityQueue;
87    ///
88    /// let mut pq: PriorityQueue<u32, u32> = PriorityQueue::new();
89    /// assert!(pq.is_empty());
90    /// pq.push(1, 10);
91    /// assert!(!pq.is_empty());
92    /// ```
93    #[inline]
94    pub fn is_empty(&self) -> bool {
95        self.heap.is_empty()
96    }
97
98    /// Returns the number of elements in the queue.
99    ///
100    /// # Examples
101    ///
102    /// ```
103    /// use graph_collections::PriorityQueue;
104    ///
105    /// let mut pq: PriorityQueue<u32, u32> = PriorityQueue::new();
106    /// pq.push(1, 5);
107    /// pq.push(2, 3);
108    /// assert_eq!(pq.len(), 2);
109    /// ```
110    #[must_use]
111    #[inline]
112    pub fn len(&self) -> usize {
113        self.heap.len()
114    }
115}
116
117impl<T: Ord, P: Ord> PriorityQueue<T, P> {
118    /// Returns a reference to the **lowest priority** value without removing it,
119    /// or `None` if empty.
120    ///
121    /// # Examples
122    ///
123    /// ```
124    /// use graph_collections::PriorityQueue;
125    ///
126    /// let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
127    /// assert_eq!(pq.peek_priority(), None);
128    /// pq.push("a", 3);
129    /// pq.push("b", 1);
130    /// assert_eq!(pq.peek_priority(), Some(&1));
131    /// assert_eq!(pq.len(), 2); // unchanged
132    /// ```
133    #[must_use]
134    #[inline]
135    pub fn peek_priority(&self) -> Option<&P> {
136        self.heap.peek().map(|(p, _)| p)
137    }
138
139    /// Returns a reference to the **value** with the lowest priority without
140    /// removing it, or `None` if empty.
141    ///
142    /// # Examples
143    ///
144    /// ```
145    /// use graph_collections::PriorityQueue;
146    ///
147    /// let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
148    /// pq.push("high", 1);
149    /// pq.push("low",  9);
150    /// assert_eq!(pq.peek_value(), Some(&"high"));
151    /// ```
152    #[must_use]
153    #[inline]
154    pub fn peek_value(&self) -> Option<&T> {
155        self.heap.peek().map(|(_, v)| v)
156    }
157}
158
159impl<T: Ord, P: Ord> PriorityQueue<T, P> {
160    /// Inserts `value` with the given `priority` in **O(log n)**.
161    ///
162    /// Duplicate priorities are allowed; ties are broken by the natural order
163    /// of `T` (because tuples are compared lexicographically).
164    ///
165    /// # Examples
166    ///
167    /// ```
168    /// use graph_collections::PriorityQueue;
169    ///
170    /// let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
171    /// pq.push("task-a", 2);
172    /// pq.push("task-b", 1);
173    /// assert_eq!(pq.peek_priority(), Some(&1));
174    /// ```
175    #[inline]
176    pub fn push(&mut self, value: T, priority: P) {
177        self.heap.push((priority, value));
178    }
179
180    /// Removes and returns `(value, priority)` for the element with the
181    /// **lowest priority**, or `None` if empty.
182    ///
183    /// # Examples
184    ///
185    /// ```
186    /// use graph_collections::PriorityQueue;
187    ///
188    /// let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
189    /// assert_eq!(pq.pop(), None);
190    /// pq.push("a", 3);
191    /// pq.push("b", 1);
192    /// pq.push("c", 2);
193    /// assert_eq!(pq.pop(), Some(("b", 1)));
194    /// assert_eq!(pq.pop(), Some(("c", 2)));
195    /// assert_eq!(pq.pop(), Some(("a", 3)));
196    /// ```
197    #[inline]
198    pub fn pop(&mut self) -> Option<(T, P)> {
199        self.heap.pop().map(|(p, v)| (v, p))
200    }
201
202    /// Removes all elements from the queue.
203    ///
204    /// # Examples
205    ///
206    /// ```
207    /// use graph_collections::PriorityQueue;
208    ///
209    /// let mut pq: PriorityQueue<u32, u32> = PriorityQueue::new();
210    /// pq.push(1, 10);
211    /// pq.push(2, 5);
212    /// pq.clear();
213    /// assert!(pq.is_empty());
214    /// ```
215    #[inline]
216    pub fn clear(&mut self) {
217        self.heap.clear();
218    }
219}
220
221impl<T: Ord, P: Ord> FromIterator<(T, P)> for PriorityQueue<T, P> {
222    /// Builds a `PriorityQueue` from an iterator of `(value, priority)` pairs.
223    ///
224    /// # Examples
225    ///
226    /// ```
227    /// use graph_collections::PriorityQueue;
228    ///
229    /// let pq: PriorityQueue<&str, u32> = vec![
230    ///     ("slow",   10u32),
231    ///     ("fast",    1),
232    ///     ("medium",  5),
233    /// ]
234    /// .into_iter()
235    /// .collect();
236    ///
237    /// assert_eq!(pq.peek_priority(), Some(&1));
238    /// assert_eq!(pq.len(), 3);
239    /// ```
240    fn from_iter<I: IntoIterator<Item = (T, P)>>(iter: I) -> Self {
241        // Swap to (P, T) for MinHeap's ordering, then wrap.
242        let heap: MinHeap<(P, T)> = iter.into_iter().map(|(v, p)| (p, v)).collect();
243        Self { heap }
244    }
245}
246
247impl<T: Ord, P: Ord> Extend<(T, P)> for PriorityQueue<T, P> {
248    /// Pushes all `(value, priority)` pairs from the iterator into the queue.
249    ///
250    /// # Examples
251    ///
252    /// ```
253    /// use graph_collections::PriorityQueue;
254    ///
255    /// let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
256    /// pq.push("seed", 5);
257    /// pq.extend([("a", 2u32), ("b", 8), ("c", 1)]);
258    /// assert_eq!(pq.peek_priority(), Some(&1));
259    /// assert_eq!(pq.len(), 4);
260    /// ```
261    fn extend<I: IntoIterator<Item = (T, P)>>(&mut self, iter: I) {
262        for (v, p) in iter {
263            self.push(v, p);
264        }
265    }
266}
graph_collections/priority_queue.rs

graph_collections/
priority_queue.rs
