Struct PriorityQueue 

pub struct PriorityQueue<T, P>
where
    T: Ord,
    P: Ord,
{ /* private fields */ }

A keyed priority queue that pops by lowest priority first.

Backed by MinHeap with (P, T) pairs. Because Rust’s tuple ordering is lexicographic, storing (priority, value) gives us priority ordering for free.

Use case

This is the queue Dijkstra’s algorithm uses: push a (node, cost) pair and always pop the cheapest node next.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();

pq.push("low",    10);
pq.push("high",    1);
pq.push("medium",  5);

assert_eq!(pq.peek_priority(), Some(&1));

assert_eq!(pq.pop(), Some(("high",   1)));
assert_eq!(pq.pop(), Some(("medium", 5)));
assert_eq!(pq.pop(), Some(("low",   10)));
assert!(pq.is_empty());

Implementations

impl<T, P> PriorityQueue<T, P>

where T: Ord, P: Ord,

pub fn new() -> PriorityQueue<T, P>

Creates a new, empty priority queue.

Examples

use graph_collections::PriorityQueue;

let pq: PriorityQueue<&str, u32> = PriorityQueue::new();
assert!(pq.is_empty());

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

Creates a new, empty priority queue with at least the given capacity pre-allocated.

Examples

use graph_collections::PriorityQueue;

let pq: PriorityQueue<u32, u32> = PriorityQueue::with_capacity(128);
assert!(pq.is_empty());

impl<T, P> PriorityQueue<T, P>

where T: Ord, P: Ord,

pub fn is_empty(&self) -> bool

Returns true if the queue contains no elements.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<u32, u32> = PriorityQueue::new();
assert!(pq.is_empty());
pq.push(1, 10);
assert!(!pq.is_empty());

pub fn len(&self) -> usize

Returns the number of elements in the queue.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<u32, u32> = PriorityQueue::new();
pq.push(1, 5);
pq.push(2, 3);
assert_eq!(pq.len(), 2);

impl<T, P> PriorityQueue<T, P>

where T: Ord, P: Ord,

pub fn peek_priority(&self) -> Option<&P>

Returns a reference to the lowest priority value without removing it, or None if empty.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
assert_eq!(pq.peek_priority(), None);
pq.push("a", 3);
pq.push("b", 1);
assert_eq!(pq.peek_priority(), Some(&1));
assert_eq!(pq.len(), 2); // unchanged

pub fn peek_value(&self) -> Option<&T>

Returns a reference to the value with the lowest priority without removing it, or None if empty.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
pq.push("high", 1);
pq.push("low",  9);
assert_eq!(pq.peek_value(), Some(&"high"));

impl<T, P> PriorityQueue<T, P>

where T: Ord, P: Ord,

pub fn push(&mut self, value: T, priority: P)

Inserts value with the given priority in O(log n).

Duplicate priorities are allowed; ties are broken by the natural order of T (because tuples are compared lexicographically).

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
pq.push("task-a", 2);
pq.push("task-b", 1);
assert_eq!(pq.peek_priority(), Some(&1));

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

Removes and returns (value, priority) for the element with the lowest priority, or None if empty.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
assert_eq!(pq.pop(), None);
pq.push("a", 3);
pq.push("b", 1);
pq.push("c", 2);
assert_eq!(pq.pop(), Some(("b", 1)));
assert_eq!(pq.pop(), Some(("c", 2)));
assert_eq!(pq.pop(), Some(("a", 3)));

pub fn clear(&mut self)

Removes all elements from the queue.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<u32, u32> = PriorityQueue::new();
pq.push(1, 10);
pq.push(2, 5);
pq.clear();
assert!(pq.is_empty());

Trait Implementations

impl<T, P> Clone for PriorityQueue<T, P>

where T: Clone + Ord, P: Clone + Ord,

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T, P> Debug for PriorityQueue<T, P>

where T: Debug + Ord, P: Debug + Ord,

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

Formats the value using the given formatter.

impl<T, P> Default for PriorityQueue<T, P>

where T: Ord, P: Ord,

fn default() -> PriorityQueue<T, P>

Returns the “default value” for a type.

impl<T, P> Extend<(T, P)> for PriorityQueue<T, P>

where T: Ord, P: Ord,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = (T, P)>,

Pushes all (value, priority) pairs from the iterator into the queue.

Examples

use graph_collections::PriorityQueue;

let mut pq: PriorityQueue<&str, u32> = PriorityQueue::new();
pq.push("seed", 5);
pq.extend([("a", 2u32), ("b", 8), ("c", 1)]);
assert_eq!(pq.peek_priority(), Some(&1));
assert_eq!(pq.len(), 4);

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, P> FromIterator<(T, P)> for PriorityQueue<T, P>

where T: Ord, P: Ord,

fn from_iter<I>(iter: I) -> PriorityQueue<T, P>

where I: IntoIterator<Item = (T, P)>,

Builds a PriorityQueue from an iterator of (value, priority) pairs.

Examples

use graph_collections::PriorityQueue;

let pq: PriorityQueue<&str, u32> = vec![
    ("slow",   10u32),
    ("fast",    1),
    ("medium",  5),
]
.into_iter()
.collect();

assert_eq!(pq.peek_priority(), Some(&1));
assert_eq!(pq.len(), 3);