Metadata-Version: 2.4
Name: fastheapdict
Version: 0.1.0
Summary: Indexed binary min-heap with permanent slot indexing for efficient decrease-key operations
Author: Hojjat Torabi Goudarzi
License-Expression: MIT
Project-URL: Homepage, https://github.com/hojjatgoudarzi/FastHeapDict
Project-URL: Repository, https://github.com/hojjatgoudarzi/FastHeapDict
Project-URL: Issues, https://github.com/hojjatgoudarzi/FastHeapDict/issues
Project-URL: Source, https://github.com/hojjatgoudarzi/FastHeapDict
Keywords: priority-queue,binary-heap,decrease-key,dijkstra,algorithms
Classifier: Development Status :: 4 - Beta
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Software Development :: Libraries
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: benchmark
Requires-Dist: pqdict; extra == "benchmark"
Requires-Dist: heapdict; extra == "benchmark"
Requires-Dist: pandas; extra == "benchmark"
Requires-Dist: matplotlib; extra == "benchmark"
Provides-Extra: test
Requires-Dist: pytest>=8; extra == "test"
Dynamic: license-file

# 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:

```bash
python -m pip install fastheapdict
```

Install from a local source checkout:

```bash
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.

```python
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:

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

## Core Operations

```python
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:

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

## Running the test suite from source

From the project root directory:

```bash
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:

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

Then run the benchmark command-line interface:

```bash
fastheapdict-benchmark --self-test --experiments all
```

You can also run the package module directly:

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

## Building and checking the distribution

From the project root directory:

```bash
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.
