Struct orx_priority_queue::DaryHeap

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

A d-ary heap which implements PriorityQueue, but not PriorityQueueDecKey.

Its interface is similar to std::collections:BinaryHeap; however, provides a generalization by allowing different d values. DaryHeapMap and DaryHeapOfIndices on the other hand, provides the additional functionality of PriorityQueueDecKey which are crucial for providing better space complexity in algorithms such as the Dijkstra’s shortest path algorithm.

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());
}

// basic d-heap without any means to located existing nodes
test_priority_queue(DaryHeap::<_, _, 4>::default());
test_priority_queue(DaryHeap::<_, _, 3>::with_capacity(16));
// using type aliases to simplify signatures
test_priority_queue(BinaryHeap::default());
test_priority_queue(BinaryHeap::with_capacity(16));
test_priority_queue(QuaternaryHeap::default());
test_priority_queue(QuaternaryHeap::with_capacity(16));
test_priority_queue(QuaternaryHeap::default());
test_priority_queue(QuaternaryHeap::with_capacity(16));

Implementations

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

where N: Clone, K: PartialOrd + Clone,

pub fn new() -> Self

Creates a new empty d-ary heap.

Examples

use orx_priority_queue::*;

let mut heap = BinaryHeap::new();

heap.push('a', 4);
heap.push('b', 42);

assert_eq!(Some('a'), heap.pop_node());
assert_eq!(Some('b'), heap.pop_node());
assert!(heap.is_empty());

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.

Examples

use orx_priority_queue::*;

// create a queue with an expected space complexity of 4
let mut queue = DaryHeap::<_, _, 4>::with_capacity(4);
queue.push('a', 4);
assert_eq!(Some('a'), queue.pop_node());

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 = QuaternaryHeapWithMap::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 DaryHeap<N, K, D>

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

fn clone(&self) -> DaryHeap<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 DaryHeap<N, K, D>

where N: Clone + 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 DaryHeap<N, K, D>

where N: Clone, K: PartialOrd + Clone,

fn default() -> Self

Returns the “default value” for a type.

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

where N: Clone, 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.