Struct orx_priority_queue::DaryHeapWithMap

pub struct DaryHeapWithMap<N, K, const D: usize = 2>
where
    N: Index,
    K: PartialOrd + Clone,
{ /* private fields */ }

A d-ary heap which implements both PriorityQueue and PriorityQueueDecKey.

See PriorityQueueDecKey for additional functionalities.

DaryHeapWithMap achieves the additional features by making use of a map of nodes to positions on the heap.

Flexibility (DaryHeapWithMap) vs Performance (DaryHeapOfIndices)

DaryHeapWithMap (hence its variants such as BinaryHeapWithMap) does not require to know the absolute size of the closed set. Furthermore, the node type needs to implement Hash + Eq rather than HasIndex trait defined in this crate. Due to these, DaryHeapWithMap might be considered as the more flexible PriorityQueueDecKey variant.

On the other hand, DaryHeapOfIndices (hence its variants such as BinaryHeapOfIndices), provides significantly faster accesses to positions of nodes on the heap. This is important for PriorityQueueDecKey operations such as decrease_key or contains. Furthermore, in many algorithms such as certain network algorithms where nodes enter and exit the queue, index_bound can often trivially be set to number of nodes.

Examples

Heap as a PriorityQueue

Usage of d-ary heap as a basic priority queue.

use orx_priority_queue::*;

fn test_priority_queue<P>(mut pq: P)
where
    P: PriorityQueue<usize, f64>
{
    pq.clear();

    pq.push(0, 42.0);
    assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&42.0), pq.peek().map(|x| x.key()));

    pq.push(1, 7.0);
    assert_eq!(Some(&1), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&7.0), pq.peek().map(|x| x.key()));

    let popped = pq.pop();
    assert_eq!(Some((1, 7.0)), popped);

    let popped = pq.pop();
    assert_eq!(Some((0, 42.0)), popped);

    assert!(pq.is_empty());
}

// d-ary heap using a hash map to locate existing nodes (although decrease-key is not used here)
test_priority_queue(DaryHeapWithMap::<_, _, 3>::default());
test_priority_queue(DaryHeapWithMap::<_, _, 4>::with_capacity(16));
// using type aliases to simplify signatures
test_priority_queue(BinaryHeapWithMap::default());
test_priority_queue(BinaryHeapWithMap::with_capacity(16));
test_priority_queue(QuarternaryHeapWithMap::default());
test_priority_queue(QuarternaryHeapWithMap::with_capacity(16));
test_priority_queue(QuarternaryHeapWithMap::default());
test_priority_queue(QuarternaryHeapWithMap::with_capacity(16));

Heap as a PriorityQueueDecKey

Usage of a d-ary heap as a priority queue with decrease key operation and its variants.

use orx_priority_queue::*;

fn test_priority_queue_deckey<P>(mut pq: P)
where
    P: PriorityQueueDecKey<usize, f64>
{
    pq.clear();

    pq.push(0, 42.0);
    assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&42.0), pq.peek().map(|x| x.key()));

    pq.push(1, 17.0);
    assert_eq!(Some(&1), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&17.0), pq.peek().map(|x| x.key()));

    pq.decrease_key(&0, 7.0);
    assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&7.0), pq.peek().map(|x| x.key()));

    let res_try_deckey = pq.try_decrease_key(&1, 20.0);
    assert_eq!(res_try_deckey, ResTryDecreaseKey::Unchanged);

    let popped = pq.pop();
    assert_eq!(Some((0, 7.0)), popped);

    let popped = pq.pop();
    assert_eq!(Some((1, 17.0)), popped);

    assert!(pq.is_empty());
}
// d-ary heap using a hash map to locate existing nodes
test_priority_queue_deckey(DaryHeapWithMap::<_, _, 3>::default());
test_priority_queue_deckey(DaryHeapWithMap::<_, _, 4>::with_capacity(16));
// using type aliases to simplify signatures
test_priority_queue_deckey(BinaryHeapWithMap::default());
test_priority_queue_deckey(BinaryHeapWithMap::with_capacity(16));
test_priority_queue_deckey(QuarternaryHeapWithMap::default());
test_priority_queue_deckey(QuarternaryHeapWithMap::with_capacity(16));
test_priority_queue_deckey(QuarternaryHeapWithMap::default());
test_priority_queue_deckey(QuarternaryHeapWithMap::with_capacity(16));

Implementations

impl<N, K, const D: usize> DaryHeapWithMap<N, K, D>

where N: Index, K: PartialOrd + Clone,

pub fn with_capacity(capacity: usize) -> Self

Creates a new d-ary heap with the given initial capacity on the number of nodes to simultaneously exist on the heap.

pub const fn d() -> usize

Returns the ‘d’ of the d-ary heap. In other words, it represents the maximum number of children that each node on the heap can have.

pub fn as_slice(&self) -> &[(N, K)]

Returns the nodes and keys currently in the queue as a slice; not necessarily sorted.

Examples

use orx_priority_queue::*;

let mut queue = QuarternaryHeapWithMap::default();
queue.push("x", 42);
queue.push("y", 7);
queue.push("z", 99);

let slice = queue.as_slice();

assert_eq!(3, slice.len());
assert!(slice.contains(&("x", 42)));
assert!(slice.contains(&("y", 7)));
assert!(slice.contains(&("z", 99)));

Trait Implementations

impl<N, K, const D: usize> Clone for DaryHeapWithMap<N, K, D>

where N: Index + Clone, K: PartialOrd + Clone + Clone,

fn clone(&self) -> DaryHeapWithMap<N, K, D>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<N, K, const D: usize> Debug for DaryHeapWithMap<N, K, D>

where N: Index + Debug, K: PartialOrd + Clone + Debug,

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

Formats the value using the given formatter.

impl<N, K, const D: usize> Default for DaryHeapWithMap<N, K, D>

where N: Index, K: PartialOrd + Clone,

fn default() -> Self

Returns the “default value” for a type.

impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeapWithMap<N, K, D>

where N: Index, K: PartialOrd + Clone,

type NodeKey<'a> = &'a (N, K) where Self: 'a, N: 'a, K: 'a

Item providing references to node & key pairs which are yielded by the iterator.

type Iter<'a> = Iter<'a, (N, K)> where Self: 'a, N: 'a, K: 'a

An iterator over the (node, key) pairs on the priority queue in an arbitrary order.

fn len(&self) -> usize

Number of elements in the queue.

fn capacity(&self) -> usize

Capacity of the heap.

fn peek(&self) -> Option<&(N, K)>

Returns, without popping, a reference to the foremost element of the queue; returns None if the queue is empty.

fn clear(&mut self)

Clears the queue.

fn pop(&mut self) -> Option<(N, K)>

Removes and returns the (node, key) pair with the lowest key in the queue; returns None if the queue is empty.

fn pop_node(&mut self) -> Option<N>

Removes and returns the node with the lowest key in the queue; returns None if the queue is empty.

fn pop_key(&mut self) -> Option<K>

Removes and returns the key of the node with the lowest key in the queue; returns None if the queue is empty.

fn push(&mut self, node: N, key: K)

Pushes the given (node, key) pair to the queue.

fn push_then_pop(&mut self, node: N, key: K) -> (N, K)

Performs the push with given (node, key) followed by the pop operation.

fn iter(&self) -> Self::Iter<'_>

Returns an iterator visiting all values on the heap in arbitrary order.

fn is_empty(&self) -> bool

Returns whether he queue is empty or not.

impl<N, K, const D: usize> PriorityQueueDecKey<N, K> for DaryHeapWithMap<N, K, D>

where N: Index, K: PartialOrd + Clone,

fn contains(&self, node: &N) -> bool

Returns whether the given node is in the queue or not.

fn key_of(&self, node: &N) -> Option<K>

Returns the key of the given node if it is in the queue; returns None otherwise.

fn decrease_key(&mut self, node: &N, decreased_key: K)

Decreases key of the node which is already in the queue to the given decreased_key.

fn update_key(&mut self, node: &N, new_key: K) -> ResUpdateKey

Updates key of the node which is already in the queue as the given new_key; and returns the result of the operation:

fn remove(&mut self, node: &N) -> K

Removes the node from the queue; and returns its current key.

fn try_decrease_key(&mut self, node: &N, new_key: K) -> ResTryDecreaseKey

Tries to decrease the key of the node which is already in the queue if its prior key is strictly larger than the new_key; otherwise, it does nothing leaving the queue unchanged.

fn decrease_key_or_push(&mut self, node: &N, key: K) -> ResDecreaseKeyOrPush

If the node is present in the queue:

fn update_key_or_push(&mut self, node: &N, key: K) -> ResUpdateKeyOrPush

If the node is present in the queue:

fn try_decrease_key_or_push( &mut self, node: &N, key: K ) -> ResTryDecreaseKeyOrPush

If the node is present in the queue, tries to decrease its key to the given key: