DepqDict

DepqDict is an efficient double-ended priority queue implemented in Python. It allows efficient retrieval and extraction of the minimum and maximum priority elements, as well as updating priorities of arbitrary elements. Implemented using a min-max heap.

Features

• Supports both min and max priority queue operations.
• Efficient push and pop operations for both min and max elements.
• Allows updating priorities of arbitrary keys.
• Implements the MutableMapping interface, behaving like a dictionary.

Installation

You can install DepqDict from PyPI using pip:

pip install depqdict

Usage

from depqdict import DepqDict

pq = DepqDict()
pq['task1'] = 5
pq['task2'] = 2
pq['task3'] = 8

print(pq.min_item())  # ('task2', 2)
print(pq.max_item())  # ('task3', 8)

pq['task1'] = 1  # Update priority
print(pq.min_item())  # ('task1', 1)

pq.pop_min_item()  # Removes ('task1', 1)

API with Runtimes

Retrieve Min/Max Items

pq.min_item()  # O(1)
pq.max_item()  # O(1)

Returns the key-value pair with the lowest or highest priority.

Remove Min/Max Items

pq.pop_min_item()  # O(log n)
pq.pop_max_item()  # O(log n)

Removes and returns the key-value pair with the lowest or highest priority.

Push-Pop Operations

pq.push_pop_min_item('task4', 3)  # O(log n)
pq.push_pop_max_item('task5', 9)  # O(log n)

Pushes a new key-priority pair into the queue and returns the smallest or largest item. Faster than using two separate operations.

Insert or Update a Key

pq['task6'] = 4  # O(log n)

Inserts or updates the priority of a key.

Delete a Key

del pq['task3']  # O(log n)

Removes a key from the queue.

License

This project is licensed under the GPL-3.0 License, as it is based on heapdict by Evgeniy Selezniov, which is also licensed under GPL-3.0. See the LICENSE file for details.

Acknowledgments

This package is based on heapdict, originally developed by Evgeniy Selezniov.