dsa_rust/composite/priority_queue.rs
1/*! An adaptable priority queue implementation
2
3# About
4This structure adds key and priority mutation as well as entry removal operations over the base [binary heap](crate::hierarchies::bin_heap) in this library. You can use the bare-bones binary heap to implement Dijkstra's algorithm, but this adaptable priority queue implementation avoids creating duplicate key entries which reduces spatial complexity and can _potentially_ improve temporal performance.
5
6The primary struct [PriorityQueue<K, P>](crate::composite::priority_queue::PriorityQueue) provides the ability to mutate both key `K` and priority `P` _after_ insertion while maintaining _O(log(n))_ (or better) operations. It is the caller's responsibility to ensure that the keying schemes they use guarantees uniqueness to maintain the structure's integrity. The structure inherits the underlying binary heap property in that equal priorities do _not_ guarantee deterministic ordering, and different insertion or removal sequences on the same set of values may yield different internal heap layouts.
7
8# Design
9The composite desgin of this structure provides _O(log(n))_ insert, remove, and key/priority mutation operations. The structure uses a `Vec`-based [heap](crate::hierarchies::bin_heap) as its primary backing and ordering structure. In addition to the heap, this design also uses a [map](crate::associative::probing_hash_table) for (private) `find(k)` opertions that run in _O(1)_ time. The map lookups allow heap mutation operaitons to avoid _O(n)_ (_n/2_ average) lookups. Due to the map's deletion logic, removed items are technically leaked which grows the map with key mutations. Key mutation operations amortize temporal complexity to _O(1)_.
10
11## Insertion
12You have the option to YOLO your way through your list by calling [put(K, P)](crate::composite::priority_queue::PriorityQueue::put) which overwrites the priorty for existing keys, or by using [try_put(K, P)](crate::composite::priority_queue::PriorityQueue::try_put) which returns [Result] if the key already exists in the queue.
13
14# Example
15
16```rust
17 use dsa_rust::composite::priority_queue::PriorityQueue;
18
19 // Build the queue
20 // NOTE: The ordering of equal priorities is NOT guaranteed
21 // Postcondition: [{Bobson, 2}, {Peter, 3}, {Brain, 3}]
22 let mut queue = PriorityQueue::<&str, u8>::new();
23 queue.put("Peter", 3);
24 queue.put("Bobson", 2);
25 queue.put("Brain", 3);
26
27 //let mut front = queue.peek().unwrap();
28 let (key, priority) = queue.peek().unwrap();
29 assert_eq!(key, &"Bobson");
30 assert_eq!(priority, &2u8); // With type specification for clarity
31
32 // Mutuate priority, bumping it to the front of the queue
33 // Postcondition: [{Peter, 1}, {Bobson, 2}, {Brain, 3}]
34 queue.mutate_priority("Peter", 1); // Mutable borrow invalidates "front"
35 let (key, priority) = queue.peek().unwrap();
36 assert_eq!(key, &"Peter");
37 assert_eq!(priority, &1);
38
39 // Key is already in the queue
40 assert!(queue.try_put("Peter", 4).is_err());
41
42 // Mutates the key at the front of the queue
43 // Postcondition: [{Piper, 1}, {Bobson, 2}, {Brain, 3}]
44 queue.mutate_key("Peter", "Piper");
45 let (key, priority) = queue.peek().unwrap();
46 assert_eq!(key, &"Piper");
47 assert_eq!(priority, &1);
48
49 // Pop the queue for owned values
50 // Postcondition: [{Bobson, 2}, {Brain, 3}]
51 let (key, priority) = queue.pop().unwrap();
52 assert_eq!(key, "Piper");
53 assert_eq!(priority, 1);
54
55 // Remove a random entry
56 // Postcondition: [{Brain, 3}]
57 assert!(queue.contains("Bobson"));
58 assert_eq!(queue.len(), 2);
59 let (key, priority) = queue.remove("Bobson").unwrap();
60 assert_eq!(key, "Bobson");
61 assert_eq!(priority, 2);
62
63 // Prove that its really gone
64 assert!(!queue.contains("Bobson"));
65 assert_eq!(queue.len(), 1);
66```
67
68*/
69
70use crate::associative::probing_hash_table::HashMap;
71use std::hash::{DefaultHasher, Hash, Hasher};
72use std::result::Result::Err;
73
74#[derive(Clone, Debug)]
75struct Entry<K, P> {
76 key: K,
77 priority: P,
78}
79
80/// # About
81///
82/// See the [module-level documentation](crate::composite::priority_queue) for more information.
83#[derive(Debug)]
84pub struct PriorityQueue<K, P>
85where
86 K: Clone + Hash,
87 P: Clone + Ord + PartialEq,
88{
89 // Sorted backing structure of key:priority pairs
90 heap: Vec<Entry<K, P>>,
91 // Tracks entry indexes in the heap as <hashed_K, index>
92 map: HashMap<usize, usize>,
93 size: usize, // # of live entries
94 deleted: usize, // # of tombstones
95}
96impl<K, P> Default for PriorityQueue<K, P>
97where
98 K: std::fmt::Debug + Clone + Hash,
99 P: Clone + std::fmt::Debug + Ord + PartialEq,
100{
101 fn default() -> Self {
102 Self::new()
103 }
104}
105impl<K, P> PriorityQueue<K, P>
106where
107 K: std::fmt::Debug + Clone + Hash,
108 P: Clone + std::fmt::Debug + Ord + PartialEq,
109{
110 // PUBLIC API
111 /////////////
112
113 /// Creates a new, zero-sized `PriorityQueue`.
114 /// Warning: Unimplemented
115 pub fn new() -> Self {
116 PriorityQueue {
117 heap: Vec::new(),
118 map: HashMap::new(),
119 size: 0,
120 deleted: 0,
121 }
122 }
123
124 /// Creates a new `PriorityQueue` that pre-allocates to the given capacity.
125 pub fn new_with_capacity(capacity: usize) -> Self {
126 PriorityQueue {
127 heap: Vec::with_capacity(capacity),
128 map: HashMap::new(),
129 size: 0,
130 deleted: 0,
131 }
132 }
133
134 /// Returns the number of live elements in the queue.
135 pub fn len(&self) -> usize {
136 self.size
137 }
138
139 /// Returns `true` if the queue is empty.
140 pub fn is_empty(&self) -> bool {
141 self.heap.is_empty() && self.map.is_empty()
142 }
143
144 /// Returns `true` if the provided key exists within the priority queue.
145 pub fn contains(&self, key: K) -> bool {
146 let hash = Self::hash(&key);
147 self.map.contains(&hash)
148 }
149
150 /// Adds an element to the heap in _O(log(n))_ time. It is the
151 /// caller's responsibility to ensure key uniqueness; this function
152 /// overwrites priority values for duplicate keys.
153 pub fn put(&mut self, key: K, priority: P) {
154 let hash = Self::hash(&key);
155
156 // Add the entry to the backing structure
157 self.heap.push(Entry { key, priority });
158
159 // Sift the entry up the heap, tracking index value
160 let index = self.sift_up(self.heap.len() - 1);
161
162 // Update the map with a unique key and the element's index value
163 self.map.put(hash, index);
164
165 self.size += 1
166 }
167
168 /// Attempts to add an element to the heap in _O(log(n))_ time.
169 /// Returns an error if the key already exists in the queue.
170 pub fn try_put(&mut self, key: K, priority: P) -> Result<(), &str> {
171 let hash = Self::hash(&key);
172
173 // Check to see if the structure already contains the element
174 // and if it does not, add it
175 if self.map.contains(&hash) {
176 Err("Error: Duplicate key detected")
177 } else {
178 // Add the entry to the backing structure
179 self.heap.push(Entry { key, priority });
180
181 // Sift the entry up the heap, tracking index value
182 let index = self.sift_up(self.heap.len() - 1);
183
184 // Update the map with a unique key and the element's index value
185 self.map.put(hash, index);
186 self.size += 1;
187
188 Ok(())
189 }
190 }
191
192 /// Returns a tuple containing an immutable reference to the data
193 /// at the top of the front of the queue in _O(1)_ time, if the
194 /// queue is not empty. Otherwise, returns `None`.
195 pub fn peek(&self) -> Option<(&K, &P)> {
196 if self.heap.is_empty() {
197 None
198 } else {
199 Some((&self.heap[0].key, &self.heap[0].priority))
200 }
201 }
202
203 /// Operates like `put(K, P)` but returns a `Result` that contains
204 /// the old priority, if it exists. Operation requires _O(log(n))_ time.
205 pub fn mutate_priority(&mut self, key: K, new_priority: P) -> Result<P, &str> {
206 let hashed_key = Self::hash(&key);
207
208 // If the key is in the system, update its priority
209 if let Some(index) = self.map.get(&hashed_key).cloned() {
210 let entry = &mut self.heap[index];
211
212 // Bind the old priority and update the entry
213 let old_priority = entry.priority.clone();
214 entry.priority = new_priority.clone();
215
216 // Re-heapify from current index
217 if new_priority < old_priority {
218 self.sift_up(index);
219 } else {
220 self.sift_down(index);
221 }
222
223 Ok(old_priority)
224 } else {
225 Err("Error: Key does not exist in the queue")
226 }
227 }
228
229 /// Attempts to replace the key in a key:value pair in the queue in _O(1)_ time,
230 /// if it exists. If the key does not exist, the operation returns an error.
231 pub fn mutate_key(&mut self, old_key: K, new_key: K) -> Result<K, &str> {
232 let hashed_old_key = Self::hash(&old_key);
233 let hashed_new_key = Self::hash(&new_key);
234
235 // Ensure the old key exists
236 if let Some(&index) = self.map.get(&hashed_old_key) {
237 // Prevent overwriting an existing key
238 if self.map.contains(&hashed_new_key) {
239 return Err("Error: New key already exists in the queue");
240 }
241
242 // Remove old key from the map
243 self.map.remove(&hashed_old_key); // Adds to tombstone count
244 self.deleted += 1;
245
246 // If tombstones out-number live entries, rehash to reduce load factor
247 //use std::mem;
248 //if self.deleted >= self.size {
249 // let old = mem::take(&mut self.map); // replaces with empty map
250 // self.map = old.rehash(); // consumes old
251 //}
252
253 // Insert new key pointing to same index
254 self.map.put(hashed_new_key, index);
255
256 // Update the heap entry
257 self.heap[index].key = new_key;
258
259 Ok(old_key)
260
261 } else {
262 Err("Error: Old key does not exist in the queue")
263 }
264 }
265
266 /// A manual tool to rehash and shrink the structure's map down to
267 /// a load factor <= 0.5. The structure automatically rehashes the underlying
268 /// map for remove and key mutation operations to reduce spatial bloat in
269 /// long-lived queues with many such mutations. This operation provides a
270 /// manual way to actually shrink the underlying map down to a load factor
271 /// of 0.5 over live entries only. This operation uses the map's
272 /// [shrink_to_fit()](crate::associative::probing_hash_table::HashMap::shrink_to_fit) operation
273 /// to clean up the backing structure for long-lived queues in _O(n)_ time
274 /// where `n` is the number of live entries in the queue.
275 pub fn clean(&mut self) {
276 use std::mem;
277 if self.map.deleted() >= self.map.len() {
278 let old = mem::take(&mut self.map); // replaces with empty map
279 self.map = old.shrink_to_fit(); // consumes old
280 }
281 }
282
283 /// Removes and returns the highest priority pair in the queue.
284 /// This operation automatically checks for spatial bloat and rehashes the
285 /// underlying map when tombstones outnumber live entries. Amortized cost
286 /// is _O(log n)_, but a rehash may occasionally incur _O(n)_ time where `n`
287 /// is the number of live entries in the queue.
288 pub fn pop(&mut self) -> Option<(K, P)> {
289 if !self.heap.is_empty() {
290 let node = self.heap.swap_remove(0); // O(1)
291 self.sift_down(0); // O(log(n))
292
293 // Rehash if tombstones out-number live entries
294 use std::mem;
295 if self.deleted >= self.size {
296 //if self.map.deleted() >= self.map.len() { // Checks take O(n) time :(
297 let old = mem::take(&mut self.map);
298 self.map = old.rehash(); // O(n)
299 }
300
301 self.size -= 1;
302 self.deleted += 1;
303 Some((node.key, node.priority))
304 } else {
305 None
306 }
307 }
308
309 /// Removes and returns an arbitrarily-located entry for the given key.
310 /// This operation automatically checks for spatial bloat and rehashes the
311 /// underlying map when tombstones outnumber live entries. Amortized cost
312 /// is _O(log n)_, but a rehash may occasionally incur _O(n)_ time where `n`
313 /// is the number of live entries in the queue.
314 pub fn remove(&mut self, key: K) -> Option<(K, P)> {
315 let hashed_key = Self::hash(&key);
316
317 // If the key is in the queue, remove it
318 if let Some(&index) = self.map.get(&hashed_key) {
319 self.map.remove(&hashed_key);
320
321 // Case 1: Removal of the last element
322 if index == self.heap.len() - 1 {
323 let removed_entry = self.heap.pop().unwrap();
324 return Some((removed_entry.key, removed_entry.priority));
325 }
326
327 // Case 2: Regular mid-structure removal
328 // swap_remove allows you to maintain O(log(n)) removals
329 // by avoiding O(n) shifts with remove
330 let removed_entry = self.heap.swap_remove(index);
331
332 // Update map for swapped item
333 let moved_key = self.heap[index].key.clone();
334 self.map.put(Self::hash(&moved_key), index);
335
336 // Decide whether to sift up or down to restore heap
337 if index > 0 {
338 let parent_index = (index - 1) / 2;
339 if self.heap[index].priority < self.heap[parent_index].priority {
340 self.sift_up(index);
341 } else {
342 self.sift_down(index);
343 }
344 } else {
345 // Root can only move down
346 self.sift_down(index);
347 }
348
349 // Check for % of tombstones and rehash to reduce load factor
350 //if self.map.len() as f64 / self.map.capacity() as f64 >= 0.5 {
351 // self.map.rehash();
352 //}
353 // Rehash if tombstones out-number live entries
354 //use std::mem;
355 //if self.map.deleted() >= self.map.len() {
356 // let old = mem::take(&mut self.map); // replaces with empty map
357 // self.map = old.rehash(); // consumes old
358 //}
359
360 self.size -= 1;
361 Some((removed_entry.key, removed_entry.priority))
362
363 // Case 3: The element doesn't exist in the queue
364 } else {
365 None // No op
366 }
367 }
368
369 // UTILITIES
370 ////////////
371
372 /// Utility function for hashing keys
373 fn hash(key: &K) -> usize {
374 // std::hash::random::DefaultHasher
375 let mut hasher = DefaultHasher::new();
376 // core::hash::Hash::hash()
377 key.hash(&mut hasher);
378 // std::hash::random::DefaultHasher::finish()
379 hasher.finish() as usize
380 }
381
382 /// Sifts a new node up the heap towards the root to maintain the heap property
383 fn sift_up(&mut self, mut index: usize) -> usize {
384 while index > 0 {
385 let parent_index = (index - 1) / 2;
386
387 if self.heap[index].priority < self.heap[parent_index].priority {
388 // Bind the keys
389 let key_child = self.heap[index].key.clone();
390 let key_parent = self.heap[parent_index].key.clone();
391
392 // Swap elements in the heap
393 self.heap.swap(index, parent_index);
394
395 // Update map after the swap
396 self.map.put(Self::hash(&key_child), parent_index);
397 self.map.put(Self::hash(&key_parent), index);
398
399 // Move to the parent's old position to continue sifting
400 index = parent_index;
401 } else {
402 break;
403 }
404 }
405 index
406 }
407
408 /// Sifts a new node downward in the tree to maintain the heap property
409 fn sift_down(&mut self, mut index: usize) -> usize {
410 loop {
411 let left_child = 2 * index + 1;
412 let right_child = 2 * index + 2;
413 let mut target = index;
414
415 // 1) Finds a target index to swap. Sibling order is not
416 // guaranteed, but you still need to check both children to
417 // ensure heap property when sifting
418 //
419 // NOTE: (Adjust < to > for a max heap)
420 if left_child < self.heap.len()
421 && self.heap[left_child].priority < self.heap[target].priority
422 {
423 target = left_child;
424 }
425 if right_child < self.heap.len()
426 && self.heap[right_child].priority < self.heap[target].priority
427 {
428 target = right_child;
429 }
430
431 // 2) If the target is not equal to the index, do the swap operation
432 // and continue sifting, otherwise the heap property is true
433 if target != index {
434 // Bind the keys
435 let key_child = self.heap[index].key.clone();
436 let key_parent = self.heap[target].key.clone();
437
438 // Swap elements in the heap
439 self.heap.swap(index, target);
440
441 // Update map after the swap
442 self.map.put(Self::hash(&key_child), target);
443 self.map.put(Self::hash(&key_parent), index);
444
445 index = target; // Move down
446 } else {
447 break; // No-op, heap is heapy 🍃🧘
448 }
449 }
450 index
451 }
452}
453
454#[cfg(test)]
455#[allow(clippy::uninlined_format_args)] // Cant inline all args in print
456mod tests {
457
458 use super::*;
459
460 /// This test uses a mock scenario of a trip booking system
461 /// where each key is a name of a person and each person
462 /// can book either economy, business, or first class ticket
463 #[test]
464 fn basic() {
465 let mut queue: PriorityQueue<&str, usize> = PriorityQueue::new();
466
467 // Initial list of passengers and their boarding groups
468 let view = [
469 ("Dichael", 3),
470 ("Sleve", 2),
471 ("Cork", 3),
472 ("Damiel", 2),
473 ("Peter", 1),
474 ("Bobson", 3),
475 ("Flank", 3),
476 ];
477
478 // Populate the queue
479 for e in view.iter() {
480 queue.put(e.0, e.1)
481 }
482
483 // Testing updated membership
484 assert!(queue.contains("Peter"));
485 assert!(queue.contains("Damiel"));
486 assert!(queue.contains("Cork"));
487 assert!(queue.contains("Dichael"));
488 assert!(queue.contains("Bobson"));
489 assert!(queue.contains("Sleve"));
490 assert!(queue.contains("Flank"));
491
492 // DEBUG PRINT: initial state
493 eprintln!("Pre-mutations: {:#?}\n{:#?}", queue.heap, queue.map.data);
494
495 // Attempt to place duplicate key:value pair
496 assert!(queue.try_put("Dichael", 2).is_err());
497
498 // Testing updated membership
499 assert!(queue.contains("Peter"));
500 assert!(queue.contains("Damiel"));
501 assert!(queue.contains("Cork"));
502 assert!(queue.contains("Dichael"));
503 assert!(queue.contains("Bobson"));
504 assert!(queue.contains("Sleve"));
505 assert!(queue.contains("Flank"));
506
507 // Attempt to mutate priority
508 assert!(queue.mutate_priority("Cork", 1).is_ok()); // increase
509 assert!(queue.mutate_priority("Damiel", 3).is_ok()); // decrease
510
511 // Testing updated membership
512 assert!(queue.contains("Peter"));
513 assert!(queue.contains("Damiel"));
514 assert!(queue.contains("Cork"));
515 assert!(queue.contains("Dichael"));
516 assert!(queue.contains("Bobson"));
517 assert!(queue.contains("Sleve"));
518 assert!(queue.contains("Flank"));
519
520 // Attempt to mutate key
521 assert!(queue.mutate_key("Peter", "The Peter").is_ok());
522 eprintln!("Mutate key: {:#?}\n{:#?}", queue.heap, queue.map.data);
523
524 // Testing updated membership
525 assert!(queue.contains("The Peter"));
526 assert!(queue.contains("Damiel"));
527 assert!(queue.contains("Cork"));
528 assert!(queue.contains("Dichael"));
529 assert!(queue.contains("Bobson"));
530 assert!(queue.contains("Sleve"));
531 assert!(queue.contains("Flank"));
532
533 // Remove passengers
534 assert_eq!(queue.remove("Sleve"), Some(("Sleve", 2)));
535 assert_eq!(queue.remove("Flank"), Some(("Flank", 3)));
536 eprintln!("Removals: {:#?}\n{:#?}", queue.heap, queue.map.data);
537
538 // Testing updated membership
539 assert!(queue.contains("The Peter"));
540 assert!(queue.contains("Damiel"));
541 assert!(queue.contains("Cork"));
542 assert!(queue.contains("Dichael"));
543 assert!(queue.contains("Bobson"));
544 assert!(!queue.contains("Sleve"));
545 assert!(!queue.contains("Flank"));
546
547 // Checks to make sure the final composition is correct.
548 // The pop operation does not guarantee ordering of
549 // equal priorities.
550 let mut passengers: Vec<(&str, usize)> = Vec::new();
551 for _ in 0..queue.heap.len() {
552 passengers.push(queue.pop().unwrap());
553 }
554
555 // DEBUG PRINT: proper priority ordering
556 eprintln!(
557 "Queue popped to list to illustrate priority ordering:\n\t{:?}",
558 passengers
559 );
560
561 // Tests to ensure updates took
562 assert!(passengers.contains(&("The Peter", 1)));
563 assert!(passengers.contains(&("Damiel", 3)));
564 assert!(passengers.contains(&("Cork", 1)));
565 assert!(passengers.contains(&("Dichael", 3)));
566
567 // Just to make sure we're not fibbin
568 assert!(!passengers.contains(&("Dichael", 2)));
569 assert!(!passengers.contains(&("Cork", 3)));
570 assert!(!passengers.contains(&("Damiel", 2)));
571 assert!(!passengers.contains(&("Peter", 1)));
572 assert!(!passengers.contains(&("Sleve", 2)));
573 assert!(!passengers.contains(&("Flank", 3)));
574
575 // Uncomment to trigger debug print
576 //panic!("MANUAL TEST FAILURE")
577
578 }
579}