Crate hashheap

source ·
Expand description

A HashHeap is a data structure that merges a priority heap with a hash table. One of the drawbacks of priority queues implemented with binary heaps is that searching requires O(n) time. Other operations such as arbitrary removal or replacement of values thus also require O(n).

In a HashHeap, however, values are paired with keys. The keys are hashable (:Hash+Eq) and the values are comparable (:Ord). Conceptually, an internal HashMap maps keys to indices of where values are stored inside an internal vector. Heap operations that require values to be swapped must keep the hashmap consistent. While the actual implementation is a bit more complicated, as it avoids all cloning, this arrangement allows search to run in (avearge-case) O(1) time. Removing or replacing a value, which will also require values to be swapped up or down the heap, can be done in O(log n) time.

Consider the possibility that the priority of objects can change. This would require finding the object then moving it up or down the queue. With most implementations of priority heaps this is only possible by removing the previous value and inserting a new one. A HashHeap can be used, for example, to effectively implement Dijkstra’s algorithm as the “open” or “tentative” queue. When a lower-cost path is found, its position in the queue must be updated. This is possible in O(log n) time with a HashHeap.

The main documentation for this create are found under struct HashHeap.

Because the mutation of values will require them to be repositioned in the heap, certain expected methods are not available, including get_mut and iter_mut. Instead, a HashHeap::modify function is provided that allows the mutation of values with a closure, and will automatically adjust their positions afterwards.

Concerning the time complexity of operations, we consider looking up a hash table to be an O(1) operation, although theoretically it can be worst-case O(n) with concocted examples. They rarely occur in practice. Thus all complexities are given as average case, unless otherwise noted. On the other hand, worst-case scenarios for binary heaps occur easily, so we note both the average and worst-case complexities when there’s a difference.

Examples

   let mut priority_map = HashHeap::<&str,u32>::new_minheap();
   priority_map.insert("A", 4);   // O(1) average, O(log n) worst
   priority_map.insert("B", 2);
   priority_map.insert("C", 1);
   priority_map.insert("D", 3);
   priority_map.insert("E", 4);
   priority_map.insert("F", 5);
   priority_map.insert("A", 6);   // insert can also modify
   assert_eq!(priority_map.peek(), Some((&"C",&1))); // O(1)
   assert_eq!(priority_map.get(&"E"), Some(&4));     // O(1)
   assert_eq!(priority_map[&"F"], 5);                // O(1)
   priority_map.modify(&"F", |v|{*v=4;});            // O(log n)
   priority_map.remove(&"E");                        // O(log n)
   assert_eq!(priority_map.pop(), Some(("C",1)));    // O(log n)
   assert_eq!(priority_map.pop(), Some(("B",2)));
   assert_eq!(priority_map.pop(), Some(("D",3)));
   assert_eq!(priority_map.pop(), Some(("F",4)));    
   assert_eq!(priority_map.pop(), Some(("A",6)));    
   assert_eq!(priority_map.len(), 0);

Structs