Metadata-Version: 2.4
Name: heap-mapping
Version: 0.2.0
Summary: An implementation of a Min-Max Heap with a MutableMapping interface.
Author-email: Andrew Tapia <andrew.tapia@uky.edu>
Project-URL: Homepage, https://github.com/actapia/min-max-heap-mapping
Project-URL: Bug Tracker, https://github.com/actapia/min-max-heap-mapping
Classifier: Programming Language :: Python :: 3
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

# heap-mapping

This is a library containing an implementation of the min-max heap data
structure, which allows for $O(1)$ retrieval and $O(log(n))$ removal of both the
minimum and maximum elements of the heap, as well as $O(log(n))$ insertion of 
keys and changes to their priorities. Heap creation can be additionally
performed in $O(n)$ time.

The data structure can be accessed as `MutableMapping`; keys are the
"values" stored in the data structure, and values are their priorities.

## Getting started

You can construct a `MinMaxHeap` from a list of values.

```python
from heap_mapping import MinMaxHeap

heap = MinMaxHeap([5, 0, 4, 1, 2, 9, 8])
print(heap.min_value) # 0
print(heap.max_value) # 9
```

By default, priorities are the same as the values.

```python
print(heap[5]) # 5
```

You can specify a key function
in the constructor to get a priority from each element.

```python
heap2 = MinMaxHeap([5, 0, 4, 1, 2, 9, 8], key=lambda x: -x)
print(heap2.min_value) # 9
print(heap2.max_value) # 0
print(heap2[5]) # -5
```

You can add elements with the `add` method. By default, the key function
specified in the constructor is used to get the priority.

```python
heap2.add(7)
print(heap2[7]) # -7
```

Alternatively, you can manually specify a key.

```python
heap2.add(6, -3)
print(heap2[6]) # -3
```

You can change the priorities after they've been inserted.

```python
heap2[7] = 1
print(heap2.max_value) # 7
```

You can look up and delete arbitrary elements in $O(log(n))$ time.

```python
del heap2[6]
print(6 in heap2) # False
```

Iteration is performed out of order. Note that this order is also *not* the
order in which the elements are stored in the heap!

```python
print(list(heap2)) # [5, 0, 4, 1, 2, 9, 8, 7]
```
