#priority #queue #binary #heap #keyed

keyed_priority_queue

Priority queue that support changing priority or early remove by key

3 unstable releases

Uses new Rust 2021

0.4.1 Oct 24, 2021
0.3.2 Feb 21, 2021
0.3.1 Dec 21, 2020
0.3.0 Oct 11, 2020
0.1.2 Nov 24, 2019

#55 in Data structures

Download history 3390/week @ 2022-03-11 4097/week @ 2022-03-18 3866/week @ 2022-03-25 5040/week @ 2022-04-01 4721/week @ 2022-04-08 4503/week @ 2022-04-15 4777/week @ 2022-04-22 5362/week @ 2022-04-29 6039/week @ 2022-05-06 5502/week @ 2022-05-13 4703/week @ 2022-05-20 4531/week @ 2022-05-27 4049/week @ 2022-06-03 4231/week @ 2022-06-10 4053/week @ 2022-06-17 3458/week @ 2022-06-24

16,338 downloads per month
Used in 13 crates (5 directly)

MIT license

72KB
1.5K SLoC

Keyed Priority Queue

Crates.io tests MIT licensed Average time to resolve an issue Percentage of issues still open

A Rust library with priority queue that supports changing of priority item in queue or early removal. To change priority you need to use some key.

Minimal supported Rust version enforced by Cargo.toml.

Usage

An example of code:

use keyed_priority_queue::{KeyedPriorityQueue, Entry};

let mut queue = KeyedPriorityQueue::new();

// Currently queue is empty
assert_eq!(queue.peek(), None);

queue.push("Second", 4);
queue.push("Third", 3);
queue.push("First", 5);
queue.push("Fourth", 2);
queue.push("Fifth", 1);

// Peek return references to most important pair.
assert_eq!(queue.peek(), Some((&"First", &5)));

assert_eq!(queue.len(), 5);

// We can clone queue if both key and priority is clonable
let mut queue_clone = queue.clone();

// We can run consuming iterator on queue,
// and it will return items in decreasing order
for (key, priority) in queue_clone{
    println!("Priority of key {} is {}", key, priority);
}

// Popping always will return the biggest element
assert_eq!(queue.pop(), Some(("First", 5)));
// We can change priority of item by key:
queue.set_priority(&"Fourth", 10);
// And get it
assert_eq!(queue.get_priority(&"Fourth"), Some(&10));
// Now biggest element is Fourth
assert_eq!(queue.pop(), Some(("Fourth", 10)));
// We can also decrease priority!
queue.set_priority(&"Second", -1);
assert_eq!(queue.pop(), Some(("Third", 3)));
assert_eq!(queue.pop(), Some(("Fifth", 1)));
assert_eq!(queue.pop(), Some(("Second", -1)));
// Now queue is empty
assert_eq!(queue.pop(), None);

// There are Entry API if you want to avoid double hash lookups
match queue.entry("Entry"){
    Entry::Vacant(entry)=>entry.set_priority(10),
    Entry::Occupied(_)=>unreachable!(),
};

match queue.entry("Entry"){
    Entry::Vacant(_)=>unreachable!(),
    Entry::Occupied(entry)=>{
        assert_eq!(entry.get_key(), &"Entry");
        assert_eq!(entry.get_priority(), &10);
        entry.set_priority(5);
    },
};

// We can clear queue
queue.clear();
assert!(queue.is_empty());

Dependencies

~515KB
~10K SLoC