Skip to main content

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.

Test Workflow Status Linting Workflow Status PyPI Publication Workflow Status Coverage Status PyPI Code style: black

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:

  1. key is any typing.Hashable object
  2. priority is a numbers.Number
  3. index is an int

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")
  • push raises KeyError if the key is already in the queue.
  • pop and peek raise IndexError if the queue is empty.
  • delete, update, index and priority raise KeyError if the key is not in the queue.
  • key raises KeyError if 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)

Source distribution for indexed-priority-queue 0.1.1
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)

Table of built distributions (wheels) for indexed-priority-queue 0.1.1
File Interpreter ABI Platform Actions
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.

Release history Release notifications | RSS feed

This release

0.1.1 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page