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.
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
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.
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)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent