Tern

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
deploy

Functions

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]) bool

Values 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.