Home › collections/priority_queue

Module collections/priority_queue

collections/priority_queue
Stability: unstable — may still change; see below.

Binary MAX-heap priority queue — Rust's BinaryHeap (D11).

Example

{ PriorityQueue } :: import("std/collections/priority_queue");

pq := PriorityQueue(i32).new();
pq.push(5);
pq.push(1);
pq.push(3);
x := pq.pop().unwrap(); // 5 — the LARGEST

For a min-heap, wrap the elements in the prelude's Reverse(T), whose Ord is the inverted one:

pq := PriorityQueue(Reverse(i32)).new();
pq.push(Reverse(i32)(5));
pq.push(Reverse(i32)(1));
x := pq.pop().unwrap().value; // 1 — the SMALLEST

Stability

unstable — the MAX-heap flip (D11) shipped in v0.2.28 and this is the campaign's one CONTESTABLE flip: priority_queue is max-ordered in C++ but MIN-ordered in Java, so the name alone does not settle which end pop should return, and Rust's BinaryHeap is what decided it here. One release of real use is what would freeze it. The rest of the surface (push/pop/peek/len/is_empty, Default, the two iterators) is settled, and Rust's into_sorted_vec/from would be additive.

Types

PriorityQueue type-function
fn(T : Type) -> Type

MAX-heap backed by an ArrayList (D11 — Rust's BinaryHeap). peek/pop yield the LARGEST element. For a min-heap, use PriorityQueue(Reverse(T)) rather than negating keys — negation is wrong for unsigned types and for the minimum of a signed type.

Type Parameters

NameTypeNotes
TTypecomptime

Trait Implementations

IntoIterator BorrowedWalk Default
impl(generic(T : Type), PriorityQueue(T), ...)
new : (fn() -> Self)

Empty queue. Allocates nothing until the first push.

Returns: Self

len : (fn(self : &Self) -> usize)

Number of elements. O(1).

Returns: usize

is_empty : (fn(self : &Self) -> bool)

True when the queue holds no elements.

Returns: bool

peek : (fn(self : &Self) -> Option(T))

The LARGEST element without removing it, or .None when empty — O(1), since the heap keeps its maximum at the root. Rust's BinaryHeap::peek.

Returns: Option(T)

push : (fn(self : &mut Self, val : T, where(T <: Ord(T))) -> unit)

Insert an element and sift it up to its place — O(log n). Rust's BinaryHeap::push.

PANICS on allocation failure, since the backing ArrayList.push does (D9); there is no try_push here.

Returns: unit

pop : (fn(self : &mut Self, where(T <: Ord(T))) -> Option(T))

Remove and return the LARGEST element, or .None when empty — O(log n). Rust's BinaryHeap::pop.

For smallest-first, build the queue over Reverse(T) rather than negating keys: negation is wrong for an unsigned type and for a signed minimum.

Returns: Option(T)

impl(generic(T : Type), where(T <: Clone), PriorityQueue(T), ...)
peek_cloned : (fn(self : &Self) -> Option(T))

A clone of the LARGEST element, or .None when empty — O(1).

Returns: Option(T)

impl(generic(T : Type), PriorityQueue(T), IntoIterator(...))
Item : T
IntoIter : PriorityQueueIter(T)
into_iter : (fn(self : Self) -> PriorityQueueIter(T))

Returns: PriorityQueueIter(T)

impl(generic(T : Type), PriorityQueue(T), ...)
iter : (fn(self : &mut Self) -> PriorityQueueIterPtr(T))

Borrowing walk over the heap array, in unsorted order (D14) — see PriorityQueueIterPtr for the invariant this can break.

Returns: PriorityQueueIterPtr(T)

impl(generic(T : Type), PriorityQueue(T), BorrowedWalk(...))
WalkCursor : usize
WalkElem : T
walk_start : (fn(self : &Self) -> usize)

The first position (equal to the end for an empty collection).

Returns: usize

walk_valid : (fn(self : &Self, cur : &usize) -> bool)

Whether cur names an element.

Parameters

NameTypeNotes
cur&usize

Returns: bool

walk_ref : (fn(self : &Self, cur : &usize) -> &T)

The element at cur, read in place (a read projection). Panics if cur names no element.

Parameters

NameTypeNotes
cur&usize

Returns: &T

walk_next : (fn(self : &Self, cur : &usize) -> usize)

The position after cur.

Parameters

NameTypeNotes
cur&usize

Returns: usize

impl(generic(T : Type), PriorityQueue(T), Default(...))
default : (fn() -> Self)

The default value of the type.

Returns: Self

PriorityQueueIter type-function
fn(T : Type) -> Type

Value iterator over a PriorityQueue — yields elements in the heap's INTERNAL array order, which is NOT sorted order (only the first element is guaranteed to be the maximum). This is what into_iter(), and therefore for(pq, ...), returns.

Rust's BinaryHeap::iter makes the same no-order promise; drain the queue with pop in a loop when the order matters.

Type Parameters

NameTypeNotes
TTypecomptime

Trait Implementations

Iterator
impl(generic(T : Type), PriorityQueueIter(T), Iterator(...))
Item : T
next : (fn(self : &mut Self) -> Option(T))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(T)

PriorityQueueIterPtr type-function
fn(T : Type) -> Type

Pointer iterator over a PriorityQueue — yields *(T) into the backing array, in the same unsorted heap order. This is what iter() returns (D14), so nothing is dup'd.

Writing through a yielded pointer can BREAK the heap invariant: nothing re-sifts afterwards. A raw view (decision 39, B7b): it holds the heap array's buffer pointer and the length iter() saw, NOT the queue, so the queue must outlive the walk, and a push or pop during it invalidates pointers already yielded.

Type Parameters

NameTypeNotes
TTypecomptime

Trait Implementations

Iterator
impl(generic(T : Type), PriorityQueueIterPtr(T), Iterator(...))
Item : *T
next : (fn(self : &mut Self) -> Option(*T))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(*T)