Struct HashHeap

Source

pub struct HashHeap<KT, VT> { /* private fields */ }

Implementations§

Source §

impl<KT: Hash + Eq, VT: PartialOrd> HashHeap<KT, VT>

Source

pub fn with_capacity(cap: usize, maxheap: bool) -> HashHeap<KT, VT>

creates a HashHeap with given capacity. If the capacity is less than 1, it defaults to 16. If the second argument is true, a maxheap is created; otherwise a minheap is created.

Source

pub fn new_minheap() -> HashHeap<KT, VT>

convenient way to create an empty min-hashheap with default capacity 16

Source

pub fn new_maxheap() -> HashHeap<KT, VT>

convenient way to create an empty max-hashheap with default capacity 16

Source

pub fn from_pairs(kvpairs: Vec<(KT, VT)>, maxheap: bool) -> HashHeap<KT, VT>

creates a min/max hashheap from a vector of key-value pairs. This operation takes O(n) time, where n is the length of vector, as it uses the well-known heapify algorithm. The second, bool argument determines if the heap portion of the structure is a maxheap (true) or minheap (false)

Source

pub fn set_hash(&mut self, h: fn(&KT) -> usize) -> bool

This function allows the user to override the default hasher provided by the Hash trait with an arbitrary function. The operation is only allowed while the HashHeap is empty. Returns true on success.

Source

pub fn set_rehash(&mut self, rh: fn(usize, usize) -> usize) -> bool

Override the default rehash method, which implements linear probing. The given function take the original hash value as the first argument and the number of collisions as the second argument. The internal representation uses the hasher from the Hash trait to compute an index, which becomes the key to a hashmap from indices to locations of keys and values. Collisions are therefore resolved by a rehashing. Example for setting a quadratic probing rehash function:

  let mut table = HashHeap::<&str,i32>::new_minheap();
  table.set_rehash(|h,c|h+c*c/2 + c/2);

The calculated hash value does not index a vector but a rust HashMap with indices as keys, so there’s no issue with out-of-bounds hash values.

Source

pub fn set_cmp(&mut self, cmp: fn(&VT, &VT) -> bool) -> bool

Override the internal comparison function with a function cmp such that cmp(a,b) is true means a is “less than” b. This operation is only allowed when the size of the HashHeap is no more than one. Returns true on success.

Source

pub fn insert(&mut self, key: KT, val: VT) -> Option<(KT, VT)>

Add or change a key-value pair, returning the replaced pair, if it exists. This operation runs in average-case O(1) time and worst-case O(log n) time. Insertion into a heap is known to be average-case O(1) because the number of values on each higher level decreases geometrically, so that the average is bounded by a convergent infinite series.

Source

pub fn push(&mut self, key: KT, val: VT) -> bool

Version of insert that does not replace existing key. Instead, it returns false if an equivalent key already exists.

Source

pub fn top_swap(&mut self, key: KT, val: VT) -> Option<(KT, VT)>

This operation replaces the top (highest priority) entry with given key and value, and returns the previous top entry. However, if the given key already exists, it replaces the existing key-value with the new ones before removing the top entry. This operation runs in O(log n) time.

Source

pub fn peek(&self) -> Option<(&KT, &VT)>

Returns the key-value pair with the highest priority value (smallest or largest depending on minheap or maxheap). This operation runs in O(1) time

Source

pub fn pop(&mut self) -> Option<(KT, VT)>

Removes and returns the key-value pair with highest priority value (smallest or largest depending on minheap or maxheap). This operation runs in O(log n) time

Source

pub fn get(&self, key: &KT) -> Option<&VT>

returns the value associated with the given key, if it exists.
Indexed access is also available, but will panic if the key is not found. This operation runs in O(1) time.

Note that there is no get_mut operation as mutations will require values to be repositioned in the heap. Call instead the HashHeap::modify operation.

Source

pub fn modify<F>(&mut self, key: &KT, mapfun: F) -> bool
where F: FnOnce(&mut VT),

This operation applies the mutating closure to the value associated with the key, if it exists. It then adjusts the position of the value inside the heap. It returns true on success and false if the key was not found. This operation runs in O(log n) time in addition to the cost of calling the closure.

Source

pub fn remove(&mut self, key: &KT) -> Option<(KT, VT)>

Removes and returns the key-value pair with the given key reference, if it exists. This operation runs in O(log n) time.

Source

pub fn contains_key(&self, key: &KT) -> bool

Determines if the given key exists in the HashHeap. This is an O(1) operation.

Source

pub fn contains_val(&self, val: &VT) -> bool

Determines if the given value exists in the table. This operation runs in O(n) time.

Source

pub fn len(&self) -> usize

returns the number of key-value pairs in the HashHeap in constant time.

Source

pub fn reserve(&mut self, additional: usize)

reserves additional capacity

Source

pub fn clear(&mut self)

clears HashHeap without changing capacity. Also resets RandomState for hasher.

Source

pub fn is_max_hashheap(&self) -> bool

returns true if the structure is a max-hashheap and false if it’s a min-hashheap.

Source §

impl<'a, KT: Hash + Eq, VT: PartialOrd> HashHeap<KT, VT>

Source

pub fn keys(&'a self) -> KeyIter<'a, KT> ⓘ

returns an iterator over the keys of the structure in no particular order

Source

pub fn values(&'a self) -> ValIter<'a, VT> ⓘ

returns an iterator over the values of the structure in no particular order

Source

pub fn iter(&'a self) -> KeyValIter<'a, KT, VT> ⓘ

returns an iterator over (key,value) pairs of the structure in no particular order.

Note that, because of the need to swap values up or down the heap after a mutation, there is no iter_mut available. Use the HashHeap::modify operation to mutate single values instead.

Source