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), 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 : 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 : 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), 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(inout(self) : 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
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
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), PriorityQueueIter(T), Iterator(...))
Item : Tnext : (fn(inout(self) : 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 push that grows the array invalidates pointers
already yielded.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), PriorityQueueIterPtr(T), Iterator(...))
Item : *Tnext : (fn(inout(self) : Self) -> Option(*T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(*T)