A priority queue built with an in-place modifiable binary heap
Project description
An priority queue built with an in-place modifiable binary heap (decrease-key,increase-key).
Operations have the following algorithmic complexities:
pop
-O(log(n))
push
-O(log(n))
(average:O(1)
)peek
-O(1)
remove
-O(log(n))
Useful for:
- Dijkstra's shortest path algorithm
- A*
- Rolling median
Install
pip install heapy
Examples
The following is an example implementation of Dijkstra's algorithm, a method
for finding the shortest path in a weighted graph. The heap-based
priority queue reduces the complexity of the basic algorithm from O(n^2)
to O(m*log(n))
, for n
nodes and m
edges.
from heapy import pqueue
def dijkstra(G, r):
'''
Find the shortest paths from a given node in a weighted graph
to every other (connected) node.
'''
todo = pqueue() # this is the heap-based priority queue
distance = {} # distances to all nodes on shortest paths
parents = { r: None } # parent pointers for all items on known shortest paths
todo.push((r, 0)) # alternate syntax: todo[r] = 0
while todo: # automatically checks len(todo) > 0
(n, d) = todo.pop() # get the minimum element; O(log(n))
distance[n] = d # save shortest distance
# update position of children in priority queue, if less
children = G.get(n, {})
for (c, w) in children.items():
if c not in distance and (c not in todo or d + w < todo[c]):
todo[c] = d + w # add or update distance ~ O(1)
parents[c] = n # update parent in minimum path distance spanning tree
return distance
Note that G
is a dictionary of dictionaries.
{
'a' : {'b' : 2, 'c' : 1},
'b' : {'a' : 2, 'd' : 3},
'c' : {'a' : 1},
'd' : {'b' : 3}
}
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file heapy-0.7.tar.gz
.
File metadata
- Download URL: heapy-0.7.tar.gz
- Upload date:
- Size: 4.2 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/32.0 requests/2.22.0 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.62.3 importlib-metadata/4.11.1 keyring/18.0.1 rfc3986/2.0.0 colorama/0.4.3 CPython/3.8.10
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 |
1687b6941b3a07bd1e4dd3a3efb30f468fcc9daaef34bfabfbfe423684ded004
|
|
MD5 |
982400d367eaafd3533ea0b04dbe6550
|
|
BLAKE2b-256 |
81f20ec1b0be0f036ae8e237850a3d0f010b4546ddb178ab1e765b0720643481
|
File details
Details for the file heapy-0.7-py3-none-any.whl
.
File metadata
- Download URL: heapy-0.7-py3-none-any.whl
- Upload date:
- Size: 4.6 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.8.0 pkginfo/1.8.2 readme-renderer/32.0 requests/2.22.0 requests-toolbelt/0.9.1 urllib3/1.26.8 tqdm/4.62.3 importlib-metadata/4.11.1 keyring/18.0.1 rfc3986/2.0.0 colorama/0.4.3 CPython/3.8.10
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 |
cffb4d3266a6dc1b20ec541b0aa18f6ee00627fd12c6467b2d896e7ab212c131
|
|
MD5 |
51e465bd095fa99cc42f0211a5720556
|
|
BLAKE2b-256 |
14ded9ed7eeb3e01aea6ece9304c280eed8951e80ffb709937f192984d839f23
|