Struct priority_queue::PriorityQueue

pub struct PriorityQueue<I, P> where
    I: Hash + Eq,  { /* fields omitted */ }

A priority queue with efficient change function to change the priority of an element.

The priority is of type P, that must implement std::cmp::Ord. The item is of typer I, that must implement Hash and Eq Implemented as an heap of indexes, stores the items inside an OrderMap to be able to retrieve them quickly.

Methods

impl<I, P> PriorityQueue<I, P> where
    P: Ord,
    I: Hash + Eq, 

fn new() -> PriorityQueue<I, P>

Creates an empty PriorityQueue

fn with_capacity(capacity: usize) -> PriorityQueue<I, P>

Creates an empty PriorityQueue with the specified capacity.

The internal collections will be able to hold at least capacity elements without reallocating. If capacity is 0, there will no allocation.

fn capacity(&self) -> usize

Returns the number of elements the internal map can hold without reallocating.

This number is a lower bound; the map might be able to hold more, but is guaranteed to be able to hold at least this many.

fn shrink_to_fit(&mut self)

Shrinks the capacity of the internal data structures that support this operation as much as possible.

fn len(&self) -> usize

Returns the number of elements in the priority queue.

fn is_empty(&self) -> bool

Returns true if the priority queue contains no elements.

fn push(&mut self, item: I, priority: P) -> Option<P>

Insert they item-priority pair into the queue.

If item was already into the queue, the old value of its priority is returned in Some; otherwise, return None.

Computes in O(log(N)) time.

fn peek(&self) -> Option<(&I, &P)>

Returns the couple (item, priority) with the greatest priority in the queue, or None if it is empty.

Computes in O(1) time

fn peek_mut(&mut self) -> Option<(&mut I, &P)>

Returns the couple (item, priority) with the greatest priority in the queue, or None if it is empty.

The item is a mutable reference, but it's a logic error to modify it in a way that change the result of Hash or Eq.

The priority cannot be modified with a call to this function. To modify the priority use ...

Computes in O(1) time

fn pop(&mut self) -> Option<(I, P)>

Trait Implementations

impl<I: Clone, P: Clone> Clone for PriorityQueue<I, P> where
    I: Hash + Eq, 

fn clone(&self) -> PriorityQueue<I, P>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<I: Debug, P: Debug> Debug for PriorityQueue<I, P> where
    I: Hash + Eq, 

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

Formats the value using the given formatter.