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 } else {
261 Err("Error: Old key does not exist in the queue")
262 }
263 }
264
265 /// A manual tool to rehash and shrink the structure's map down to
266 /// a load factor <= 0.5. The structure automatically rehashes the underlying
267 /// map for remove and key mutation operations to reduce spatial bloat in
268 /// long-lived queues with many such mutations. This operation provides a
269 /// manual way to actually shrink the underlying map down to a load factor
270 /// of 0.5 over live entries only. This operation uses the map's
271 /// [shrink_to_fit()](crate::associative::probing_hash_table::HashMap::shrink_to_fit) operation
272 /// to clean up the backing structure for long-lived queues in _O(n)_ time
273 /// where `n` is the number of live entries in the queue.
274 pub fn clean(&mut self) {
275 use std::mem;
276 if self.map.deleted() >= self.map.len() {
277 let old = mem::take(&mut self.map); // replaces with empty map
278 self.map = old.shrink_to_fit(); // consumes old
279 }
280 }
281
282 /// Removes and returns the highest priority pair in the queue.
283 /// This operation automatically checks for spatial bloat and rehashes the
284 /// underlying map when tombstones outnumber live entries. Amortized cost
285 /// is _O(log n)_, but a rehash may occasionally incur _O(n)_ time where `n`
286 /// is the number of live entries in the queue.
287 pub fn pop(&mut self) -> Option<(K, P)> {
288 if !self.heap.is_empty() {
289 let node = self.heap.swap_remove(0); // O(1)
290 self.sift_down(0); // O(log(n))
291
292 // Rehash if tombstones out-number live entries
293 use std::mem;
294 if self.deleted >= self.size {
295 //if self.map.deleted() >= self.map.len() { // Checks take O(n) time :(
296 let old = mem::take(&mut self.map);
297 self.map = old.rehash(); // O(n)
298 }
299
300 self.size -= 1;
301 self.deleted += 1;
302 Some((node.key, node.priority))
303 } else {
304 None
305 }
306 }
307
308 /// Removes and returns an arbitrarily-located entry for the given key.
309 /// This operation automatically checks for spatial bloat and rehashes the
310 /// underlying map when tombstones outnumber live entries. Amortized cost
311 /// is _O(log n)_, but a rehash may occasionally incur _O(n)_ time where `n`
312 /// is the number of live entries in the queue.
313 pub fn remove(&mut self, key: K) -> Option<(K, P)> {
314 let hashed_key = Self::hash(&key);
315
316 // If the key is in the queue, remove it
317 if let Some(&index) = self.map.get(&hashed_key) {
318 self.map.remove(&hashed_key);
319
320 // Case 1: Removal of the last element
321 if index == self.heap.len() - 1 {
322 let removed_entry = self.heap.pop().unwrap();
323 return Some((removed_entry.key, removed_entry.priority));
324 }
325
326 // Case 2: Regular mid-structure removal
327 // swap_remove allows you to maintain O(log(n)) removals
328 // by avoiding O(n) shifts with remove
329 let removed_entry = self.heap.swap_remove(index);
330
331 // Update map for swapped item
332 let moved_key = self.heap[index].key.clone();
333 self.map.put(Self::hash(&moved_key), index);
334
335 // Decide whether to sift up or down to restore heap
336 if index > 0 {
337 let parent_index = (index - 1) / 2;
338 if self.heap[index].priority < self.heap[parent_index].priority {
339 self.sift_up(index);
340 } else {
341 self.sift_down(index);
342 }
343 } else {
344 // Root can only move down
345 self.sift_down(index);
346 }
347
348 // Check for % of tombstones and rehash to reduce load factor
349 //if self.map.len() as f64 / self.map.capacity() as f64 >= 0.5 {
350 // self.map.rehash();
351 //}
352 // Rehash if tombstones out-number live entries
353 //use std::mem;
354 //if self.map.deleted() >= self.map.len() {
355 // let old = mem::take(&mut self.map); // replaces with empty map
356 // self.map = old.rehash(); // consumes old
357 //}
358
359 self.size -= 1;
360 Some((removed_entry.key, removed_entry.priority))
361
362 // Case 3: The element doesn't exist in the queue
363 } else {
364 None // No op
365 }
366 }
367
368 // UTILITIES
369 ////////////
370
371 /// Utility function for hashing keys
372 fn hash(key: &K) -> usize {
373 // std::hash::random::DefaultHasher
374 let mut hasher = DefaultHasher::new();
375 // core::hash::Hash::hash()
376 key.hash(&mut hasher);
377 // std::hash::random::DefaultHasher::finish()
378 hasher.finish() as usize
379 }
380
381 /// Sifts a new node up the heap towards the root to maintain the heap property
382 fn sift_up(&mut self, mut index: usize) -> usize {
383 while index > 0 {
384 let parent_index = (index - 1) / 2;
385
386 if self.heap[index].priority < self.heap[parent_index].priority {
387 // Bind the keys
388 let key_child = self.heap[index].key.clone();
389 let key_parent = self.heap[parent_index].key.clone();
390
391 // Swap elements in the heap
392 self.heap.swap(index, parent_index);
393
394 // Update map after the swap
395 self.map.put(Self::hash(&key_child), parent_index);
396 self.map.put(Self::hash(&key_parent), index);
397
398 // Move to the parent's old position to continue sifting
399 index = parent_index;
400 } else {
401 break;
402 }
403 }
404 index
405 }
406
407 /// Sifts a new node downward in the tree to maintain the heap property
408 fn sift_down(&mut self, mut index: usize) -> usize {
409 loop {
410 let left_child = 2 * index + 1;
411 let right_child = 2 * index + 2;
412 let mut target = index;
413
414 // 1) Finds a target index to swap. Sibling order is not
415 // guaranteed, but you still need to check both children to
416 // ensure heap property when sifting
417 //
418 // NOTE: (Adjust < to > for a max heap)
419 if left_child < self.heap.len()
420 && self.heap[left_child].priority < self.heap[target].priority
421 {
422 target = left_child;
423 }
424 if right_child < self.heap.len()
425 && self.heap[right_child].priority < self.heap[target].priority
426 {
427 target = right_child;
428 }
429
430 // 2) If the target is not equal to the index, do the swap operation
431 // and continue sifting, otherwise the heap property is true
432 if target != index {
433 // Bind the keys
434 let key_child = self.heap[index].key.clone();
435 let key_parent = self.heap[target].key.clone();
436
437 // Swap elements in the heap
438 self.heap.swap(index, target);
439
440 // Update map after the swap
441 self.map.put(Self::hash(&key_child), target);
442 self.map.put(Self::hash(&key_parent), index);
443
444 index = target; // Move down
445 } else {
446 break; // No-op, heap is heapy 🍃🧘
447 }
448 }
449 index
450 }
451}
452
453#[cfg(test)]
454#[allow(clippy::uninlined_format_args)] // Cant inline all args in print
455mod tests {
456
457 use super::*;
458
459 /// This test uses a mock scenario of a trip booking system
460 /// where each key is a name of a person and each person
461 /// can book either economy, business, or first class ticket
462 #[test]
463 fn basic() {
464 let mut queue: PriorityQueue<&str, usize> = PriorityQueue::new();
465
466 // Initial list of passengers and their boarding groups
467 let view = [
468 ("Dichael", 3),
469 ("Sleve", 2),
470 ("Cork", 3),
471 ("Damiel", 2),
472 ("Peter", 1),
473 ("Bobson", 3),
474 ("Flank", 3),
475 ];
476
477 // Populate the queue
478 for e in view.iter() {
479 queue.put(e.0, e.1)
480 }
481
482 // Testing updated membership
483 assert!(queue.contains("Peter"));
484 assert!(queue.contains("Damiel"));
485 assert!(queue.contains("Cork"));
486 assert!(queue.contains("Dichael"));
487 assert!(queue.contains("Bobson"));
488 assert!(queue.contains("Sleve"));
489 assert!(queue.contains("Flank"));
490
491 // DEBUG PRINT: initial state
492 eprintln!("Pre-mutations: {:#?}\n{:#?}", queue.heap, queue.map.data);
493
494 // Attempt to place duplicate key:value pair
495 assert!(queue.try_put("Dichael", 2).is_err());
496
497 // Testing updated membership
498 assert!(queue.contains("Peter"));
499 assert!(queue.contains("Damiel"));
500 assert!(queue.contains("Cork"));
501 assert!(queue.contains("Dichael"));
502 assert!(queue.contains("Bobson"));
503 assert!(queue.contains("Sleve"));
504 assert!(queue.contains("Flank"));
505
506 // Attempt to mutate priority
507 assert!(queue.mutate_priority("Cork", 1).is_ok()); // increase
508 assert!(queue.mutate_priority("Damiel", 3).is_ok()); // decrease
509
510 // Testing updated membership
511 assert!(queue.contains("Peter"));
512 assert!(queue.contains("Damiel"));
513 assert!(queue.contains("Cork"));
514 assert!(queue.contains("Dichael"));
515 assert!(queue.contains("Bobson"));
516 assert!(queue.contains("Sleve"));
517 assert!(queue.contains("Flank"));
518
519 // Attempt to mutate key
520 assert!(queue.mutate_key("Peter", "The Peter").is_ok());
521 eprintln!("Mutate key: {:#?}\n{:#?}", queue.heap, queue.map.data);
522
523 // Testing updated membership
524 assert!(queue.contains("The Peter"));
525 assert!(queue.contains("Damiel"));
526 assert!(queue.contains("Cork"));
527 assert!(queue.contains("Dichael"));
528 assert!(queue.contains("Bobson"));
529 assert!(queue.contains("Sleve"));
530 assert!(queue.contains("Flank"));
531
532 // Remove passengers
533 assert_eq!(queue.remove("Sleve"), Some(("Sleve", 2)));
534 assert_eq!(queue.remove("Flank"), Some(("Flank", 3)));
535 eprintln!("Removals: {:#?}\n{:#?}", queue.heap, queue.map.data);
536
537 // Testing updated membership
538 assert!(queue.contains("The Peter"));
539 assert!(queue.contains("Damiel"));
540 assert!(queue.contains("Cork"));
541 assert!(queue.contains("Dichael"));
542 assert!(queue.contains("Bobson"));
543 assert!(!queue.contains("Sleve"));
544 assert!(!queue.contains("Flank"));
545
546 // Checks to make sure the final composition is correct.
547 // The pop operation does not guarantee ordering of
548 // equal priorities.
549 let mut passengers: Vec<(&str, usize)> = Vec::new();
550 for _ in 0..queue.heap.len() {
551 passengers.push(queue.pop().unwrap());
552 }
553
554 // DEBUG PRINT: proper priority ordering
555 eprintln!(
556 "Queue popped to list to illustrate priority ordering:\n\t{:?}",
557 passengers
558 );
559
560 // Tests to ensure updates took
561 assert!(passengers.contains(&("The Peter", 1)));
562 assert!(passengers.contains(&("Damiel", 3)));
563 assert!(passengers.contains(&("Cork", 1)));
564 assert!(passengers.contains(&("Dichael", 3)));
565
566 // Just to make sure we're not fibbin
567 assert!(!passengers.contains(&("Dichael", 2)));
568 assert!(!passengers.contains(&("Cork", 3)));
569 assert!(!passengers.contains(&("Damiel", 2)));
570 assert!(!passengers.contains(&("Peter", 1)));
571 assert!(!passengers.contains(&("Sleve", 2)));
572 assert!(!passengers.contains(&("Flank", 3)));
573
574 // Uncomment to trigger debug print
575 //panic!("MANUAL TEST FAILURE")
576 }
577}