Crate hashheap

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.

Two versions of the data structure are provided. Their documentation are found under structs HashHeap and ConstHashHeap. The consthashheap module was added in Version 0.2.

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

   use hashheap::*;
   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);

   // version of structure with const capacity 8:
   let mut points = ConstHashHeap::<&str,f32,8>::new(true); // true=maxheap
   points.insert("mary",3.0);
   points.insert("larz",2.0);
   points.insert("narx",2.5);
   points.insert("parv",3.4);
   let mut morepoints = points.resize::<16>();  //to larger capacity
   morepoints.insert("oarw",3.7);
   morepoints.insert("qaru",2.6);
   morepoints.insert("nev",0.2);
   morepoints = morepoints.refresh();
   morepoints.remove(&"narx");
   morepoints.modify(&"larz",|x|*x += 1.2);
   assert_eq!(morepoints.get(&"qaru"), Some(&2.6));
   assert_eq!(morepoints.get(&"larz"), Some(&3.2));
   assert!(morepoints.get(&"narx").is_none());
   assert_eq!(morepoints.pop(), Some(("oarw",3.7)));
   assert_eq!(morepoints.size(), 5);

Re-exports

pub use consthashheap::*;

Modules

consthashheap

This module contains a new implementation of the hashed heap structure, ConstHashHeap. The main external difference is that the capacity of the structure must be known at compile time. However, a ConstHashHeap::resize function is provided to transfer entries to a structure of higher capacity. There are also many internal changes that should improve performance. Rust HashMaps are no longer employed anywhere. Instead, each ConstHashHeap contains two arrays, keys and values. The keys array contains (Option) entries of the form (key,vi) where vi is the index in the values array that contains the mapped value. The values array contains entries of the form (value,ki) where ki is the index in the keys array of the corresponding key. The keys array is treated as a closed hashmap (open addressing) with a linear probing rehash function. The values array is treated as a binary heap. Swapping values in the values array updates the corresponding information in the keys array using the ki index which it possesses. The ki index does not change until the entire structure is resized.

Structs

HashHeap

IntoIter

Consuming iterator, type for IntoIterator. This iterator will call HashHeap::pop for the next (key,value) pair, and will thus return the values in sorted order (increasing for min-hashheap, decreasing for max-hashheap). The cost of any for-loop over this iterator is thus at least O(n*log n). In constrast, the non-consuming iterators all enumerate references in arbitrary order.

KeyIter

This iterator is returned by the HashHeap::keys function

KeyValIter

This iterator is returned by the HashHeap::iter function

PriorityQueue

Non-consuming iterator, but will empty the heap via pop()

ValIter

This iterator is returned by the HashHeap::values function