python-rheaps

Python bindings for rheaps, a Rust library of heap / priority-queue data structures, built with PyO3 and maturin. rheaps is itself a Rust port of JHeaps; this package gives Python the same broad selection of heap algorithms as native, object-oriented classes.

Features

• 31 heap classes across four families: array-backed, tree-based, DAG-based, and monotone radix heaps.
• Flexible keys. Every general-purpose heap accepts key_type=int, key_type=float, or the default key_type=object (any Python object, ordered via its own __lt__/__eq__, exactly like heapq). int/float keys use Rust's native comparisons with no per-comparison Python callback.
• Arbitrary values. Every entry can carry an arbitrary Python object as its value (defaults to None if omitted), independent of the key type.
• Checked handles. Addressable heaps return a handle from insert() used to inspect, update, decrease, or delete that entry later. A handle is rejected with ValueError if it's stale (its entry was removed, or the heap was cleared) or belongs to a different heap instance.
• No garbage collection surprises. Heap state lives inside the Rust object; there's no manual cleanup, close(), or context manager to remember.

Installation

Not yet published to PyPI. Build and install from source with maturin:

python3 -m venv .venv
source .venv/bin/activate
pip install maturin
maturin develop          # builds the extension and installs it into the venv
# maturin develop --release   # for an optimized build

Requires a Rust toolchain (stable, edition 2024 support — 1.88+) to build.

Quick start

A plain, value-only heap (like heapq, but with more algorithm choices):

import rheaps

heap = rheaps.BinaryArrayHeap()
heap.push(4)
heap.push(1)
heap.push(3)

assert heap.peek() == 1
assert heap.pop() == 1
assert heap.pop() == 3

An addressable heap, where insert() returns a handle you can use later:

heap = rheaps.PairingHeap()
task = heap.insert(10, "compile report")
heap.insert(5, "answer mail")

heap.decrease_key(task, 1)
assert heap.peek() == (task, 1, "compile report")
assert heap.delete(task) == (1, "compile report")
assert heap.pop() == (5, "answer mail")

Melding combines two heaps of the same class and key_type. The donor is left as a valid, empty heap afterward — Python has no move semantics, so unlike Rust's rheaps (which makes reusing a melded-away heap a compile error), reusing the donor here is well-defined, just empty:

a = rheaps.PairingHeap()
a.insert(3)
a.insert(5)

b = rheaps.PairingHeap()
deadline = b.insert(4)
b.insert(9)

a.meld(b)               # b's entries move into a; handles b issued stay valid
a.decrease_key(deadline, 1)

assert [a.pop()[0] for _ in range(4)] == [1, 3, 5, 9]
assert len(b) == 0      # b is still a usable, empty PairingHeap

Note that insert() (not push()) is the entry point for every addressable heap in the table below — push/peek/pop (no handle) are reserved for the plain, value-only heaps.

Choosing a key type

rheaps.BinaryArrayHeap()                    # key_type=object (default): any comparable Python object
rheaps.BinaryArrayHeap(key_type=int)        # native i64 keys, fastest
rheaps.BinaryArrayHeap(key_type=float)      # native finite f64 keys, fastest

key_type is fixed for the lifetime of the heap (chosen once at construction) and two heaps must share it to meld(). Comparing incompatible objects under key_type=object raises TypeError, the same as it would from plain a < b.

Choosing an implementation

Every class above except the radix heaps takes key_type=int|float|object (default object); radix heaps have a fixed native key type baked into the class name instead, since their bucket structure depends on it.

API reference

Value-only heaps (Heap-shaped: BinaryArrayHeap, DaryArrayHeap, the weak heaps, MinMaxBinaryArrayDoubleEndedHeap, SoftHeap)

MinMaxBinaryArrayDoubleEndedHeap additionally has peek_max()/pop_max(). SoftHeap additionally has rank_limit() and a fallible meld(other) (see Soft heaps below).

Addressable heaps (everything else, except radix heaps)

* Only on classes that support that capability — see the table above (SoftAddressableHeap has no decrease_key; the non-meldable classes have no meld).

Radix heaps (monotone)

Radix heaps enforce that removed keys are nondecreasing: once a key is popped, no smaller key may be inserted or decrease_key'd below it. They also require a fixed inclusive [minimum_key, maximum_key] range at construction. Violating either raises ValueError.

Soft heaps

SoftHeap/SoftAddressableHeap implement a Kaplan-Zwick soft heap: in exchange for faster operations, up to error_rate (a fraction between 0 and 1, exclusive) of keys may be corrupted (silently increased) at any time. Use them when an approximately-correct minimum is acceptable — for example, as a building block inside a minimum spanning tree algorithm. Neither supports decrease_key, since corruption means the heap no longer tracks each entry's exact position.

Error handling

Development

python3 -m venv .venv
source .venv/bin/activate
pip install maturin pytest
maturin develop
pytest

tests/test_large_scale.py ports the large-scale conformance invariants rheaps' own Rust test suite exercises against each implementation (thousands of ascending/random/decreasing-key operations checked against a plain sorted() oracle, arbitrary-order deletion, melding, and — for soft heaps — the weaker "every inserted key eventually comes back out, in some order" invariant that corruption permits) across every parametrized heap class. It runs as part of the same pytest invocation (a few extra seconds), not a separate opt-in suite.

The Rust source lives in src/:

• key.rs — the int/float/object key representations and conversions.
• error.rs — rheaps error types → Python exceptions.
• handles.rs — one #[pyclass] per rheaps handle type.
• macros.rs — shared codegen: each heap-trait shape (Heap, AddressableHeap + DecreaseKeyHeap, MeldableAddressableHeap, DoubleEndedAddressableHeap, and the radix-heap shapes) gets one macro that a concrete heap module composes.
• heaps/{array,tree,dag,monotone}.rs — the 31 concrete heap classes, mostly a handful of lines each invoking the shared macros.

Documentation

Full documentation (API reference, tutorials, and an example gallery) is built with Sphinx:

source .venv/bin/activate
pip install -e ".[docs]"     # sphinx, sphinx-rtd-theme, sphinx-gallery, matplotlib, pillow
make -C docs html

The rendered pages land in docs/_build/html/index.html. The source lives in docs/:

• docs/api/ — introduction.rst (heap inventory by family), heaps.rst and handles.rst (autoclass reference for every heap and handle class).
• docs/tutorials/ — a walkthrough of the addressable-heap API (insert/peek/decrease_key/delete/meld).
• docs/install.rst, docs/license.rst, docs/credits.rst.

examples/ holds the sphinx-gallery scripts rendered into that documentation build (addressable/, array/, monotone/, one plain, runnable .py file per example) — run any of them directly with python3 examples/addressable/plot_pairing.py without building the docs.

Relationship to rheaps and JHeaps

This package is a thin PyO3 wrapper: it doesn't reimplement any algorithm, it just exposes the rheaps crate — an idiomatic Rust port of JHeaps — as Python classes. If you use this library, consider citing the paper describing the algorithms and implementation set it's 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

License

Copyright 2024-2026 Dimitrios Michail

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this project's files except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0, or see the LICENSE file in this repository.

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0