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 additonal 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, 42.0)), pq.peek());

    pq.push(1, 7.0);
    assert_eq!(Some(&(1, 7.0)), pq.peek());

    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(TernaryHeap::default());
test_priority_queue(TernaryHeap::with_capacity(16));
test_priority_queue(QuarternaryHeap::default());
test_priority_queue(QuarternaryHeap::with_capacity(16));

Implementations

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

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

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.

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,

fn len(&self) -> usize

Number of elements in the queue.

fn capacity(&self) -> usize

Capacity of the heap.

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

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

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 is_empty(&self) -> bool

Returns whether he queue is empty or not.