pub trait PriorityQueue<N, K>: Clonewhere
    K: PartialOrd,{
    // Required methods
    fn len(&self) -> usize;
    fn as_slice(&self) -> &[(N, K)];
    fn peek(&self) -> Option<&(N, K)>;
    fn clear(&mut self);
    fn pop(&mut self) -> Option<(N, K)>;
    fn pop_node(&mut self) -> Option<N>;
    fn pop_key(&mut self) -> Option<K>;
    fn push(&mut self, node: N, key: K);
    fn push_then_pop(&mut self, node: N, key: K) -> (N, K);

    // Provided method
    fn is_empty(&self) -> bool { ... }
}
Expand description

A priority queue which allows pushing (N, K)=(node, key) pairs to the collection, and popping the foremost element having the lowest key.

Required Methods§

source

fn len(&self) -> usize

Number of elements in the queue.

source

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

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

source

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.

source

fn clear(&mut self)

Clears the queue.

source

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.

source

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.

source

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.

source

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

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

source

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

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

Since the queue cannot be empty after the push, the return type is not optional.

The reason of merging the calls is that handling two instructions at once is more efficient for certain implementations, such as for the binary heap.

Provided Methods§

source

fn is_empty(&self) -> bool

Returns whether he queue is empty or not.

Object Safety§

This trait is not object safe.

Implementors§

source§

impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeap<N, K, D>where N: Clone, K: PartialOrd + Clone,

source§

impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeapOfIndices<N, K, D>where N: HasIndex, K: PartialOrd + Clone,

source§

impl<N, K, const D: usize> PriorityQueue<N, K> for DaryHeapWithMap<N, K, D>where N: Eq + Hash + Clone, K: PartialOrd + Clone,