# rheaps
[](https://github.com/d-michail/rheaps/actions/workflows/ci.yml)
[](LICENSE)
`rheaps` is a collection of heap and priority-queue data structures written in
Rust. It is an idiomatic Rust port of the
[JHeaps](https://github.com/d-michail/jheaps) library and includes array,
tree, DAG, double-ended, addressable, meldable, soft, and monotone heaps behind
a small set of common traits.
The crate is licensed under the Apache License, Version 2.0.
## What is this library?
This library provides several heap implementations with well-defined Rust
interfaces. It is intended for applications and experiments that need more
than a conventional binary priority queue—for example, stable handles,
efficient melding, access to both extrema, monotone keys, or a particular heap
algorithm.
- Keys use their `Ord` implementation, and duplicate keys are permitted.
- Queries borrow their result; removals return owned values.
- Empty-heap operations return `None`.
- Addressable heaps return checked opaque handles.
- Meldable heaps preserve handles from the donor heap after a successful meld.
- Constructors validate parameters such as d-ary degrees, soft-heap error
rates, and radix-heap key bounds.
## What is a heap?
A heap is a priority queue containing elements whose keys come from a totally
ordered set. A min-oriented heap supports these core operations:
- create an empty heap;
- insert an element;
- inspect the element with the smallest key;
- remove the element with the smallest key;
- query its size or whether it is empty; and
- remove all elements.
Some implementations provide additional operations:
- **Addressable heaps** return handles that can be used to inspect, update, or
delete individual entries.
- **Meldable heaps** efficiently combine two heaps of the same concrete type.
- **Double-ended heaps** expose both the minimum and maximum.
- **Monotone heaps** exploit the guarantee that newly inserted keys are not
smaller than the last key removed.
- **Soft heaps** permit controlled key corruption in exchange for useful
amortized performance bounds.
## Choosing an implementation
| [`array`](src/array) | `BinaryArrayHeap`, `DaryArrayHeap`, weak heaps | the smallest, cache-friendly heap for `push`/`pop`, optionally addressable |
| [`tree`](src/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`](src/dag) | `HollowHeap` | meld and decrease-key without cutting nodes from a parent |
| [`monotone`](src/monotone) | radix heaps over `u32`, `u64`, `FiniteF64`, and `BigUint` | keys are removed in nondecreasing order, e.g. Dijkstra's algorithm |
See [Implementations](#implementations) below for the full list, and each
type's rustdoc for the traits it implements.
## Installation
The crate uses Rust 2024 edition. To use the current repository version, add:
```toml
[dependencies]
rheaps = { git = "https://github.com/d-michail/rheaps" }
```
To build and test a checkout:
```console
git clone https://github.com/d-michail/rheaps.git
cd rheaps
cargo test --all-targets
```
### Optional features
- `serde` — adds `Serialize`/`Deserialize` implementations for every heap,
handle, and key type in the crate, so a populated heap can be persisted and
reloaded. Enable it with:
```toml
[dependencies]
rheaps = { version = "0.16", features = ["serde"] }
```
## Compatibility
`rheaps` is pre-1.0 and follows Cargo's `0.x` convention: breaking changes
may land in any `0.x` release rather than only at a major version bump.
Once the crate reaches `1.0`, renamed or removed public items will go
through a deprecation cycle before removal, and releases will follow
semantic versioning.
## Quick start
All ordinary heaps are min-oriented according to the key type's `Ord`
implementation.
```rust
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));
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(4));
assert_eq!(heap.pop(), None);
```
### Addressable heaps
An addressable heap associates each key with a value and returns a handle for
the entry. Handles are rejected if they are stale or belong to another heap.
```rust
use rheaps::AddressableHeap;
use rheaps::array::BinaryArrayAddressableHeap;
let mut heap = BinaryArrayAddressableHeap::new();
let task = heap.insert(10, "compile report");
heap.insert(5, "answer mail");
heap.decrease_key(task, 1).unwrap();
assert_eq!(
heap.peek().map(|(_, key, value)| (*key, *value)),
Some((1, "compile report")),
);
assert_eq!(heap.delete(task), Ok((1, "compile report")));
```
### Alternative ordering
To select a different priority order, wrap the key in a type with the desired
`Ord` implementation. The standard library's `Reverse` wrapper turns any
min-oriented heap into a max-oriented heap.
```rust
use std::cmp::Reverse;
use rheaps::Heap;
use rheaps::array::BinaryArrayHeap;
let mut heap = BinaryArrayHeap::new();
heap.push(Reverse(1));
heap.push(Reverse(4));
heap.push(Reverse(3));
assert_eq!(heap.pop(), Some(Reverse(4)));
```
### Melding heaps
A meldable heap efficiently absorbs 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; any handles it had already issued stay valid through
the receiver.
```rust
use rheaps::{Heap, MeldableHeap};
use rheaps::tree::PairingHeap;
let mut a = PairingHeap::new();
a.push(3);
a.push(5);
let mut b = PairingHeap::new();
b.push(1);
b.push(4);
a.meld(b); // b is moved here and can no longer be used
assert_eq!(a.pop(), Some(1));
```
### Double-ended heaps
A double-ended heap gives efficient access to both the minimum and the
maximum without maintaining two separate heaps.
```rust
use rheaps::{DoubleEndedHeap, Heap};
use rheaps::array::MinMaxBinaryArrayDoubleEndedHeap;
let mut heap = MinMaxBinaryArrayDoubleEndedHeap::new();
heap.push(4);
heap.push(1);
heap.push(3);
assert_eq!(heap.peek(), Some(&1));
assert_eq!(heap.peek_max(), Some(&4));
assert_eq!(heap.pop_max(), Some(4));
```
### Monotone radix heaps
Radix heaps require explicit inclusive key bounds and reject insertions that
fall outside those bounds or violate monotonicity.
```rust
use rheaps::monotone::U32RadixHeap;
let mut heap = U32RadixHeap::new(0, 1_000).unwrap();
heap.try_push(12).unwrap();
heap.try_push(7).unwrap();
assert_eq!(heap.pop(), Some(7));
// After removing 7, keys below 7 are no longer valid.
assert!(heap.try_push(6).is_err());
```
Floating-point radix heaps use `FiniteF64`, which provides a total order and
rejects NaN and infinite values before insertion.
```rust
use rheaps::monotone::{F64RadixHeap, FiniteF64};
let zero = FiniteF64::new(0.0).unwrap();
let ten = FiniteF64::new(10.0).unwrap();
let mut heap = F64RadixHeap::new(zero, ten).unwrap();
heap.try_push(FiniteF64::new(2.5).unwrap()).unwrap();
assert_eq!(heap.pop().map(FiniteF64::into_inner), Some(2.5));
```
## Implementations
### Array-based
- `BinaryArrayHeap`
- `DaryArrayHeap`
- `BinaryArrayAddressableHeap`
- `DaryArrayAddressableHeap`
- `BinaryArrayWeakHeap`
- `BinaryArrayBulkInsertWeakHeap`
- `BinaryArrayIntegerValueHeap`
- `MinMaxBinaryArrayDoubleEndedHeap`
### Tree-based
- `BinaryTreeAddressableHeap`
- `DaryTreeAddressableHeap`
- `BinaryTreeSoftHeap`
- `BinaryTreeSoftAddressableHeap`
- `LeftistHeap`
- `SkewHeap`
- `PairingHeap`
- `PurePairingHeap`
- `RankPairingHeap`
- `CostlessMeldPairingHeap`
- `FibonacciHeap`
- `SimpleFibonacciHeap`
- `StrictFibonacciHeap`
The leftist, skew, pairing, and Fibonacci families are addressable and
meldable. The soft and explicit tree heaps expose the capabilities appropriate
to their algorithms.
### DAG-based
- `HollowHeap`, an addressable and meldable hollow heap with lazy reclamation
of hollow nodes
### Double-ended
- `MinMaxBinaryArrayDoubleEndedHeap`
- `ReflectedFibonacciHeap`
- `ReflectedPairingHeap`
The reflected heaps are addressable and meldable and support minimum and
maximum access together with both `decrease_key` and `increase_key`.
### Monotone
Each supported key family has value-less and addressable variants:
- `U32RadixHeap` and `U32RadixAddressableHeap` for `u32`;
- `U64RadixHeap` and `U64RadixAddressableHeap` for `u64`;
- `F64RadixHeap` and `F64RadixAddressableHeap` for `FiniteF64`; and
- `BigUintRadixHeap` and `BigUintRadixAddressableHeap` for
`num_bigint::BigUint`.
## Common interfaces
The crate root defines the shared traits:
- `Heap` and `ValueHeap`;
- `AddressableHeap`;
- `DoubleEndedHeap` and `DoubleEndedAddressableHeap`;
- `MeldableHeap` and `MeldableAddressableHeap`;
- `MeldableDoubleEndedAddressableHeap`; and
- `TryHeap`, `TryAddressableHeap`, and `TryDecreaseKeyHeap`, fallible
counterparts to `Heap`/`AddressableHeap`/`DecreaseKeyHeap` for heap
families - currently only the radix heaps in `monotone` - whose insertion
can fail because of algorithm-specific key restrictions.
Concrete types also provide inherent methods, so callers can use a heap
directly without writing generic code. Addressable operations report invalid,
foreign, and stale handles explicitly. Removing an entry or clearing a heap
invalidates its handle. Melding takes the donor heap by value, so reusing it
afterward is a compile-time error, while its existing handles remain usable
through the receiver.
Array-backed heaps implement `FromIterator` and `Extend`. Collecting into a
d-ary heap uses the binary degree of two; extending an existing d-ary heap
preserves its configured degree. Addressable variants collect and extend
`(key, value)` pairs.
## Relationship to JHeaps
The implementation set and much of the behavioral test coverage are derived
from [JHeaps](https://github.com/d-michail/jheaps). The API follows Rust's
ownership, trait, and error-handling conventions rather than reproducing the
Java API literally. All public heap implementations in JHeaps are represented
in this crate. Behavioral coverage is tracked at the shared-fixture level—one
Rust conformance fixture exercised against every implementation it applies
to—rather than as a method-by-method mapping to JHeaps' Java test suite.
## 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](https://doi.org/10.1016/j.softx.2021.100869)
```bibtex
@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},
}
```
## License
Copyright (C) 2014–2026 Dimitrios Michail
Licensed under the Apache License, Version 2.0. See [LICENSE](LICENSE) for the
full license text.