## 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

- 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). - This iterator is returned by the HashHeap::keys function
- This iterator is returned by the HashHeap::iter function
- This iterator is returned by the HashHeap::values function