pqueue
The pqueue module is a priority queue: values of any type, each pushed with a priority (an int, float or string), taken out lowest priority first (queue) or highest first (queue_max). The priority comes first, as in Python's heapq tuples. It's what Dijkstra's algorithm, schedulers and event loops need.
import pqueue
struct Job:
name: str
tries: int
fn main():
q = pqueue.queue[int, Job]()
q.push(3, Job("deploy", 0))
q.push(1, Job("build", 0))
q.push(2, Job("test", 1))
print(q.peek_priority(), q.len())
while q.pop() is Some(j):
print(j.name)Output
Some(1) 3
build
test
deployFunctions
fn queue[P: Ord, T]() PriorityQueue[P, T] lowest priority first
fn queue_max[P: Ord, T]() PriorityQueue[P, T] highest priority first
fn push[P: Ord, T](q: mut PriorityQueue[P, T], priority: P, value: T)
fn pop[P: Ord, T](q: mut PriorityQueue[P, T]) Option[T]
fn peek[P, T](q: PriorityQueue[P, T]) Option[T]
fn peek_priority[P, T](q: PriorityQueue[P, T]) Option[P]
fn len[P, T](q: PriorityQueue[P, T]) int
fn is_empty[P, T](q: PriorityQueue[P, T]) boolValues with equal priorities come out in no particular order. For shortest paths, push a node again when its distance improves and skip it on the way out if it's stale:
import pqueue
fn main():
# edges[u] holds (v, weight) pairs
edges = [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], []]
dist = [0, 1000, 1000, 1000]
q = pqueue.queue[int, int]()
q.push(0, 0)
while q.peek_priority() is Some(d):
u = q.pop().unwrap()
if d > dist[u]:
continue
for e in edges[u]:
if d + e.1 < dist[e.0]:
dist[e.0] = d + e.1
q.push(dist[e.0], e.0)
print(dist)Output
[0, 3, 1, 4]Speed
A 4-ary heap, like heap's, kept as two arrays (priorities and values). bench/std runs Dijkstra on a 1000 x 1000 grid: Tern 29.3 ms, Rust's BinaryHeap of tuples 32.2 ms, Go's container/heap 108 ms.