Module collections/priority_queue
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
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
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
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)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
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 : TIntoIter : 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)
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
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
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)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(T : Type), where(T <: Clone), PriorityQueueIter(T), Iterator(...))
Item : Tnext : (fn(self : &mut Self) -> Option(T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(T)
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
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
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)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(T : Type), PriorityQueueIterPtr(T), Iterator(...))
Item : *Tnext : (fn(self : &mut Self) -> Option(*T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(*T)
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
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
p | Origin | comptime |
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)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
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))