Struct addressable_pairing_heap::PairingHeap

pub struct PairingHeap<T, K> where
    K: Key,  { /* fields omitted */ }

An addressable pairing heap implementation.

Stores elements with an associated key. The key can be thought of as the priority of the element that is associated to it.

Supports usages like take_min that takes the element with the minimum key out of this storage.

Inserting elements into this data structure provides the caller with handles that makes accessing the elements possible - this is called "addressable". Handles are always local to the associated pairing heap instance and thus should not be exchanged throughout various instances of pairing heaps.

An special feature of addressable pairing heaps is the possibility to explicitely decrease the key of an already stored element with the decrease_key operation which simply increases the priority of the associated element.

It is possible to use different implementations for Key as the key type.

Methods

impl<T, K> PairingHeap<T, K> where
    K: Key, 

fn new() -> Self

Creates a new instance of a PairingHeap.

fn len(&self) -> usize

Returns the number of elements stored in this PairingHeap.

fn is_empty(&self) -> bool

Returns true if this PairingHeap is empty.

fn push(&mut self, elem: T, key: K) -> Handle

Inserts the given element into the PairingHeap with its associated key and returns a Handle to it that allows to directly address it.

The handle is for example required in order to use methods like decrease_key.

fn decrease_key(&mut self, handle: Handle, new_key: K) -> Result<()>

Decreases the key of the element with the associated given handle. Will panic if the given new key is not lower than the previous key.

fn get(&self, handle: Handle) -> Option<&T>

Returns a reference to the element associated with the given handle.

fn get_mut(&mut self, handle: Handle) -> Option<&mut T>

Returns a mutable reference to the element associated with the given handle.

unsafe fn get_unchecked(&self, handle: Handle) -> &T

Returns a reference to the element associated with the given handle.

Does not perform bounds checking so use it carefully!

unsafe fn get_unchecked_mut(&mut self, handle: Handle) -> &mut T

Returns a mutable reference to the element associated with the given handle.

Does not perform bounds checking so use it carefully!

fn peek(&self) -> Option<&T>

Returns a reference to the current minimum element if not empty.

unsafe fn peek_unchecked(&self) -> &T

Returns a reference to the current minimum element.

Does not perform bounds checking so use it carefully!

fn peek_mut(&mut self) -> Option<&mut T>

Returns a mutable reference to the current minimum element if not empty.

unsafe fn peek_unchecked_mut(&mut self) -> &mut T

Returns a reference to the current minimum element without bounds checking. So use it very carefully!

fn pop(&mut self) -> Option<T>

Removes the element associated with the minimum key within this PairingHeap and returns it.

unsafe fn pop_unchecked(&mut self) -> T

Removes the element associated with the minimum key within this PairingHeap without checking for emptiness and returns it.

So use this method carefully!

fn values<'a>(&'a self) -> Values<'a, T, K>

Iterate over the values in this PairingHeap by reference in unspecified order.

fn values_mut<'a>(&'a mut self) -> ValuesMut<'a, T, K>

Iterate over the values in this PairingHeap by mutable reference unspecified order.

fn drain_min(self) -> DrainMin<T, K>

Iterate over values stored within a PairingHeap in a sorted-by-min order. Drains the heap.

Trait Implementations

impl<T: Debug, K: Debug> Debug for PairingHeap<T, K> where
    K: Key, 

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Clone, K: Clone> Clone for PairingHeap<T, K> where
    K: Key, 

fn clone(&self) -> PairingHeap<T, K>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T, K> Index<Handle> for PairingHeap<T, K> where
    K: Key, 

type Output = T

The returned type after indexing

fn index(&self, handle: Handle) -> &Self::Output

The method for the indexing (container[index]) operation

impl<T, K> IndexMut<Handle> for PairingHeap<T, K> where
    K: Key, 

fn index_mut(&mut self, handle: Handle) -> &mut Self::Output

The method for the mutable indexing (container[index]) operation