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

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

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), Default(...))
default : (fn() -> Self)

The default value of the type.

Returns: Self

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

Returns: PriorityQueueIter(T)

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.

It holds the queue by handle and yields a clone of each element (T <: Clone): the backing list is a value since B8, so the queue keeps its own.

Type Parameters

NameTypeNotes
TTypecomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

impl(generic(T : Type), where(T <: Clone), 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

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

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)

PriorityQueueCursor type-function
fn(T : Type, p : Origin) -> Type

The shared walk over a PriorityQueue (Rust's Iter<'a, T>): a &(PriorityQueue(T), p) lend and a position, yielding each element as a &(T, p). Binding the cursor freezes the collection for its life (E0911 on a write), which is what makes the borrowed for(&xs, x => body) lower to the value form over (&xs).into_iter().

Type Parameters

NameTypeNotes
TTypecomptime
pOrigincomptime

Trait Implementations

impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unit

Write a clone of self into the uninitialized slot dst, which has room for size_of_val(self) bytes at align_of_val(self).

Parameters

NameTypeNotes
selfSelf
dst*(Self)

Returns: unit

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

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

Returns: Option(&(T, p))