Struct KeyValueHeap 

pub struct KeyValueHeap<Key, Value> { /* private fields */ }

A max-heap which allows for generalised Keys (required to implement StorageKey) and Values (which are required to be ordered, divisible and addable).

Implementations

impl<Key, Value> KeyValueHeap<Key, Value>

where Key: StorageKey + Copy, Value: AddAssign<Value> + DivAssign<Value> + PartialOrd + Default + Copy,

pub fn get_value(&self, key: Key) -> &Value

pub fn pop_max(&mut self) -> Option<Key>

Deletes the key with maximum value from the heap and returns it, or None if the heap is empty.

The time-complexity of this operation is O(logn).

pub fn increment(&mut self, key: Key, increment: Value)

Increments the value of the element of ‘key’ by ‘increment’

The worst-case time-complexity of this operation is O(logn); average case is likely to be better

pub fn restore_key(&mut self, key: Key)

Restores the entry with key ‘key’ to the heap if the key is not present, otherwise does nothing. Its value is the previous value used before ‘delete_key’ was called.

The run-time complexity of this operation is O(logn)

pub fn delete_key(&mut self, key: Key)

Removes the entry with key ‘key’ (temporarily) from the heap if the key is present, otherwise does nothing. Its value remains recorded internally and is available upon calling KeyValueHeap::restore_key. The value can still be subjected to KeyValueHeap::divide_values.

The run-time complexity of this operation is O(logn)

pub fn len(&self) -> usize

Returns how many elements are in the heap (including the (temporarily) “removed” values)

pub fn is_empty(&self) -> bool

Returns whether there are no elements in the heap (including the (temporarily) “removed” values)

pub fn num_nonremoved_elements(&self) -> usize

pub fn is_key_present(&self, key: Key) -> bool

Returns whether the key is currently not (temporarily) remove

pub fn grow(&mut self, key: Key, value: Value)

Increases the size of the heap by one and adjust the data structures appropriately by adding Key and Value

pub fn clear(&mut self)

pub fn divide_values(&mut self, divisor: Value)

Divides all the values in the heap by ‘divisor’. This will also affect the values of keys that have been KeyValueHeap::delete_key.

The run-time complexity of this operation is O(n)

Trait Implementations

impl<Key: Clone, Value: Clone> Clone for KeyValueHeap<Key, Value>

fn clone(&self) -> KeyValueHeap<Key, Value>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Key: Debug, Value: Debug> Debug for KeyValueHeap<Key, Value>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Key: StorageKey, Value> Default for KeyValueHeap<Key, Value>

fn default() -> Self

Returns the “default value” for a type.