Python Indexed Priority Queue
A Python implementation of an Indexed Priority Queue (IPQ).
An IPQ is like any regular priority queue. But it supports quick lookups, updates and deletions...on the fly.
Time and space complexities
It is implemented as minimum binary heap. For indexing, it uses two additional dicts. So, in terms of memory space, it uses O(3 * n) -> O(n) space.
This data structure has the following time complexities:
| Operation | Description | Time Complexity |
|---|---|---|
push(key, priority) |
Enqueue a key with a priority | O(log(n)) |
pop() -> key, priority |
Pop and retrieve the index with the highest priority (lowest value) | O(log(n)) |
peek() -> key, priority |
Retrieve the key and priority with the highest priority, without popping it | O(1) |
delete(key) -> key, priority |
Delete a key | O(log(n)) |
update(key, new_priority) |
Update the priority of a key | O(log(n)) |
index(key) -> int |
Retrieve the index of the given key | O(1) |
key(index: int) |
Retrieve the key at the given index | O(1) |
priority(key) |
Retrieve the priority of the given key | O(1) |
__bool__ -> bool |
Determine if the queue is empty or not. Equivalent to is_empty() | O(1) |
__len__ -> int |
Returns the count of elements in the queue | O(1) |
__contains(key)__ -> bool |
Determine if the given key exists in the queue | O(1) |
Where:
keyis anytyping.Hashableobjectpriorityis anumbers.Numberindexis anint
Examples
from indexed_priority_queue import IndexedPriorityQueue
# Initialize the queue
queue = IndexedPriorityQueue()
# Enqueue a few values
queue.push("John", 7)
queue.push("Maria", 3)
queue.push("Peter", 5)
key, priority = queue.peek() # Maria, 3
queue.push("Kim", 2)
key, priority = queue.peek() # Kim, 2
queue.update("Peter", 1)
key, priority = queue.peek() # Peter, 1
assert len(queue) == 4 # True
key, priority = queue.delete("John") # John, 7
assert len(queue) == 3 # True
key, priority = queue.pop() # Peter, 1
key, priority = queue.peek() # Kim, 2
index = queue.index("Kim") # 0
key = queue.key(0) # Kim
priority = queue.priority("Kim") # 2
# Not empty, 2
if queue:
print(f"Not empty, {len(queue)}")
else:
print("Empty")
# Max is not in the queue
if "Max" in queue:
print("Max is in the queue")
else:
print("Max is not in the queue")
pushraisesKeyErrorif the key is already in the queue.popandpeekraiseIndexErrorif the queue is empty.delete,update,indexandpriorityraiseKeyErrorif the key is not in the queue.keyraisesKeyErrorif the given index does not exist.
Use any hashable object as key
You can use any typing.Hashable object as key, not just strings. For example:
queue.push(frozenset(["a", "b"]), 1)
queue.push((1, 2, 3), 2)
Metadata
Release files for indexed-priority-queue 0.1.1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| indexed_priority_queue-0.1.1.tar.gz | 11.4 kB | Without provenance | Details for indexed_priority_queue-0.1.1.tar.gz |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| indexed_priority_queue-0.1.1-py3-none-any.whl | Python 3 | none | any | Details for indexed_priority_queue-0.1.1-py3-none-any.whl |
Total release size: 16.3 kB
Release files / indexed_priority_queue-0.1.1.tar.gz
| Download URL | indexed_priority_queue-0.1.1.tar.gz |
|---|---|
| Size | 11.4 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
02c1b1e29bec9561c156bd387b2afc99f031f393f1615d7e490ca5ea653867af
|
|
BLAKE2b-256 checksum How to use checksums |
8c272b9e6fe38550a020a190dfe911da8361f598aec3e48fada5d4cc16d5927c
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.11.3
|
Release files / indexed_priority_queue-0.1.1-py3-none-any.whl
| Download URL | indexed_priority_queue-0.1.1-py3-none-any.whl |
|---|---|
| Size | 5.0 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
086e6e4eea8e3de0dbbffc0fbfe561460ec9a960b529f373cc014486f21f6f22
|
|
BLAKE2b-256 checksum How to use checksums |
70af89fe055b26037d5df4e3e243cea3b8f94c2df05a3f260c7ac2a8c82fc222
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.1 CPython/3.11.3
|
Security for indexed-priority-queue 0.1.1
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.