Crate rheaps 

Heap and priority-queue data structures for Rust.

rheaps is an idiomatic Rust port of JHeaps, a mature Java heap library. It packages array, tree, DAG, double-ended, addressable, meldable, soft, and monotone heaps behind a small set of common traits, so generic code can be written against a capability (say, AddressableHeap) instead of a concrete type.

Quick start

use rheaps::Heap;
use rheaps::array::BinaryArrayHeap;

let mut heap = BinaryArrayHeap::new();
heap.push(4);
heap.push(1);
heap.push(3);

assert_eq!(heap.peek(), Some(&1));
assert_eq!(heap.pop(), Some(1));

Choosing an implementation

Module	Representative types	Reach for it when you need
array	BinaryArrayHeap, DaryArrayHeap, weak heaps	the smallest, cache-friendly heap for push/pop, optionally addressable
tree	leftist, skew, pairing, rank-pairing, Fibonacci, soft, and reflected heaps	efficient meld, amortized O(1) decrease-key, or both minimum and maximum access
dag	HollowHeap	meld and decrease-key without cutting nodes from a parent
monotone	radix heaps over u32, u64, FiniteF64, and BigUint	keys are removed in nondecreasing order, e.g. Dijkstra’s algorithm

Each module’s own documentation lists its concrete types and the common traits each one implements.

Concepts

• Ordering. Keys use their Ord implementation, and duplicate keys are permitted. Wrap a key in a newtype (or std::cmp::Reverse) to change its priority order; for example, Reverse turns any min-oriented heap into a max-oriented one.
• Handles. AddressableHeap::insert returns an opaque, Copy handle used to inspect, update, or delete that entry later. A handle is rejected once its entry is removed, its heap is cleared, or it is presented to a different heap instance. Key decreases are a separate capability, DecreaseKeyHeap: a handle-based heap that cannot restore heap order after a decrease simply does not implement it.
• Melding. MeldableHeap::meld and its addressable and double-ended counterparts efficiently absorb another heap of the same concrete type by taking it by value. The donor is moved into the call, so reusing it afterward is a compile-time error rather than a runtime one; handles the donor already issued stay valid through the receiver.
• Fallibility. Ordinary heaps implement the infallible Heap and AddressableHeap and never fail to insert. Radix heaps in monotone are the exception: their constructors validate key bounds, and insertion enforces monotonicity, so they implement TryHeap, TryAddressableHeap, and TryDecreaseKeyHeap instead, reporting violations through Result rather than panicking.

Relationship to JHeaps

The implementation set and much of the behavioral test coverage are derived from JHeaps. The API follows Rust’s ownership, trait, and error-handling conventions rather than reproducing the Java API literally.

Cite

If you use this library, please cite the paper describing the algorithms and implementation set it is derived from:

D. Michail. JHeaps: An open-source library of priority queues. SoftwareX, 16:100869, 2021. https://doi.org/10.1016/j.softx.2021.100869

@article{michail2021jheaps,
      title={JHeaps: An open-source library of priority queues},
      author={Michail, Dimitrios},
      journal={SoftwareX},
      volume={16},
      pages={100869},
      year={2021},
      publisher={Elsevier},
      doi={10.1016/j.softx.2021.100869},
      url={https://doi.org/10.1016/j.softx.2021.100869},
}

Optional features

• serde - implements Serialize/Deserialize for every heap, handle, and key type in the crate.

Re-exports

pub use error::DecreaseKeyError;

pub use error::IncreaseKeyError;

pub use error::InvalidHandle;

Modules

array

Array-backed heap implementations.

dag

Directed-acyclic-graph heap implementations.

error

Error types shared by every addressable-heap capability.

monotone

Monotone radix heaps for unsigned integers, finite floating-point keys, and arbitrary-sized unsigned integers.

tree

Tree-based heap implementations.

Macros

impl_double_ended_heap_via_addressable

Implements DoubleEndedHeap<T> for $ty<T, ()> by forwarding to its DoubleEndedAddressableHeap<T, ()> implementation. See impl_heap_via_addressable for why this is a macro rather than a blanket impl.

impl_heap_via_addressable

Implements Heap<T> for $ty<T, ()> by forwarding to its AddressableHeap<T, ()> implementation.

impl_meldable_heap_via_addressable

Implements MeldableHeap<T> for $ty<T, ()> by forwarding to its MeldableAddressableHeap<T, ()> implementation. See impl_heap_via_addressable for why this is a macro rather than a blanket impl.

Traits

AddressableHeap

A min-oriented heap whose entries are addressed by stable handles.

DecreaseKeyHeap

An addressable heap that supports decreasing a live entry’s key.

DoubleEndedAddressableHeap

An addressable heap that supports efficient access to both extrema.

DoubleEndedHeap

A heap that supports efficient access to both extrema.

Heap

The common interface implemented by min-oriented heaps.

MeldableAddressableHeap

An addressable heap that can efficiently meld another heap.

MeldableDoubleEndedAddressableHeap

A double-ended addressable heap that can efficiently meld another heap.

MeldableHeap

A heap that can efficiently combine its contents with another heap of the same concrete type.

TryAddressableHeap

A min-oriented heap whose entries are addressed by stable handles and whose insertion can fail because of algorithm-specific key restrictions.

TryDecreaseKeyHeap

A TryAddressableHeap that supports decreasing a live entry’s key, reporting the same key restrictions as insertion.

TryHeap

A heap whose insertion can fail because of algorithm-specific key restrictions.

ValueHeap

A min-oriented heap that associates each key with a value.