keyed_priority_queue

keyed_priority_queue is a Rust library providing a priority queue whose entries are addressable by key, so you can change an item’s priority or remove it early without a linear scan. Standard binary heaps only expose the top element; this crate keeps a key-to-position index alongside an editable binary heap to make targeted updates efficient.

It exposes a KeyedPriorityQueue with an Entry-style API for pushing, peeking, popping, and updating priorities, making it well suited to algorithms like Dijkstra’s shortest path or A* where node priorities are repeatedly relaxed.

What You Get

• A KeyedPriorityQueue with push, pop, and peek operations
• Change-priority updates addressed by key
• Early removal of arbitrary items by key
• An Entry-style API for conditional insertion and updates
• Efficient key lookup backed by indexmap

Common Use Cases

• Implementing Dijkstra’s or A* with priority relaxation by node
• Task schedulers that reprioritize or cancel queued items
• Event simulations where pending events change priority
• Any workload needing a heap with keyed updates

Under The Hood

Architecture - The core lives in the keyed_priority_queue workspace member: keyed_priority_queue.rs exposes the public type, editable_binary_heap.rs implements a binary heap whose elements can be repositioned in place, and mediator.rs coordinates the key-to-heap-position mapping so updates by key stay O(log n). This pairing of an index map with a mutable heap is what enables change-priority and remove-by-key.

Tech Stack - Rust (2021 edition, rust-version 1.81) organized as a Cargo workspace with the library and a benches member. Its only runtime dependency is indexmap, used to map keys to their current heap slot; the heap itself is hand-written rather than delegated.

Code Quality - The repository has cross-platform CI, a CHANGELOG, and a benches/ crate for performance measurement, and the heap logic is split into focused modules (heap, mediator, queue). Community activity is modest, but the code is mature and stable with a clear separation between the index and the heap.

API Design - The KeyedPriorityQueue API mirrors familiar collection methods (push, pop, peek) and adds an Entry API for ergonomic conditional updates, so reprioritizing a node reads naturally. Documentation on docs.rs and README examples cover the common patterns; the main conceptual step for users is that every value is addressed by a distinct key.