Crate priority_queue

This crate provides 2 main data structures:

• a priority queue
• a double priority queue.

Both data structures are backed by an hashmap, allowing to change the priority of an element with some efficient methods in O(log(N)) time (worst case).

The elements (called Items, of type I) must implement Hash and Eq traits.

This can frequently be achieved by using #[derive(PartialEq, Eq, Hash)]. If you implement these yourself, it is important that the following property holds:

k1 == k2 -> hash(k1) == hash(k2)

In other words, if two keys are equal, their hashes must be equal.

The priority P may be any type that implements Ord. For reverse order remember the standard wrapper Reverse<T>

Examples

use priority_queue::PriorityQueue;

let mut pq = PriorityQueue::new();

assert!(pq.is_empty());
pq.push("Apples", 5);
pq.push("Bananas", 8);
pq.push("Strawberries", 23);

assert_eq!(pq.peek(), Some((&"Strawberries", &23)));

pq.change_priority("Bananas", 25);
assert_eq!(pq.peek(), Some((&"Bananas", &25)));

for (item, _) in pq.into_sorted_iter() {
    println!("{}", item); // Will print Bananas, Strawberries, Apples
}

Reverse ordering

use priority_queue::PriorityQueue;
use std::cmp::Reverse;

let mut pq = PriorityQueue::new();

assert!(pq.is_empty());
pq.push("Apples", Reverse(5));
pq.push("Bananas", Reverse(8));
pq.push("Strawberries", Reverse(23));

assert_eq!(pq.peek(), Some((&"Apples", &Reverse(5))));

for (item, _) in pq.into_sorted_iter() {
    println!("{}", item); // Will print Apples, Bananas, Strawberries
}

Re-exports

pub use crate::double_priority_queue::DoublePriorityQueue;

pub use crate::priority_queue::PriorityQueue;

Modules

core_iterators

This module defines iterator types that are used with both the PriorityQueue and the DoublePriorityQueue

double_priority_queue

This module contains the DoublePriorityQueue type and the related iterators.

priority_queue

This module contains the PriorityQueue type and the related iterators.

Structs

TryReserveError