fastheapdict 0.1.0

Indexed binary min-heap with permanent slot indexing for efficient decrease-key operations

FastHeapDict

FastHeapDict is a high-performance indexed priority queue for Python designed for algorithms that repeatedly update priorities. Unlike duplicate-entry priority queues, FastHeapDict maintains a single active heap entry for each key, providing efficient decrease_key operations while avoiding stale entries and unnecessary heap growth. It is particularly well suited for graph algorithms such as Dijkstra's shortest-path algorithm, A*, Prim's algorithm, event simulation, and scheduling applications.

Requirements

• Python 3.10 or newer

Installation

Install from PyPI:

python -m pip install fastheapdict

Install from a local source checkout:

python -m pip install -e .

Project links

• GitHub repository: https://github.com/hojjatgoudarzi/FastHeapDict
• Issues: https://github.com/hojjatgoudarzi/FastHeapDict/issues

A Complete Example: Dijkstra's Shortest-Path Algorithm

The example below demonstrates the intended use of FastHeapDict in Dijkstra's algorithm.

from fastheapdict import FastHeapDict

def dijkstra(graph, source):
    dist = {v: float("inf") for v in graph}
    dist[source] = 0

    pq = FastHeapDict()
    pq[source] = 0

    while pq:
        u, du = pq.popitem()

        if du > dist[u]:
            continue

        for v, w in graph[u]:
            nd = du + w

            if nd < dist[v]:
                dist[v] = nd
                pq.decrease_key(v, nd)

    return dist


graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 5), ("D", 10)],
    "C": [("E", 3)],
    "D": [("F", 11)],
    "E": [("D", 4)],
    "F": []
}

print(dijkstra(graph, "A"))

Output:

{'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}

Core Operations

from fastheapdict import FastHeapDict

pq = FastHeapDict()

pq["alice"] = 8
pq["bob"] = 3

pq.decrease_key("alice", 2)

key, priority = pq.popitem()

print(key, priority)

Operation	Complexity
Insert / Update	O(log n)
decrease_key	O(log n)
popitem	O(log n)
Key lookup	O(1)

When should I use FastHeapDict?

FastHeapDict is intended for problems in which priorities change frequently. Typical applications include shortest-path algorithms, minimum spanning trees, informed graph search, discrete-event simulation, and scheduling. If your application repeatedly inserts duplicate entries into a standard heap to emulate decrease-key, FastHeapDict can simplify the implementation and reduce unnecessary heap growth.

Running the bundled example from source

From the project root directory, install the package in editable mode first and then run the example:

python -m pip install -e .
python examples/basic_usage.py

Running the test suite from source

From the project root directory:

python -m pip install -e ".[test]"
python -m pytest

Benchmarks

The source distribution includes the benchmark programs used to evaluate the implementation. They reproduce the experiments described in the accompanying project report and compare FastHeapDict against alternative priority-queue implementations.

To install the optional benchmark dependencies from a source checkout, run:

python -m pip install -e ".[benchmark]"

Then run the benchmark command-line interface:

fastheapdict-benchmark --self-test --experiments all

You can also run the package module directly:

python -m fastheapdict --self-test --experiments all

Building and checking the distribution

From the project root directory:

python -m pip install --upgrade build twine
rm -rf dist build src/*.egg-info
python -m build
python -m twine check dist/*

License

MIT License.