heap
A priority queue on <.
Generated from spec/std/heap.cp by cpl doc --format json.
Heap
pub struct Heap<T>A priority queue on <. push and pop are O(log n), peek is O(1); memory is one list.
For a mixed order put desc(x) in the entry: Heap<(Int, Desc<V>)>() pops the
smallest distance first and, among equals, the largest vertex.
Heap.new
fn new<K>(by: ?(T -> K) = None) -> Heap<T>Create an empty Heap<T>, optionally ordered by key extractor by: (W7).
With by: f the heap compares f(x), and f is called on every comparison, so it
should be cheap (a field, desc). Without by: it compares the elements themselves.
- cost: O(1)
- traps: never
Examples:
var h: Heap<Int> = Heap(); h.push(3); h.push(1); h.pop() == Some(1)var h: Heap<Int> = Heap(by: desc); h.push(1); h.push(3); h.pop() == Some(3)
Heap.of
fn of<K>(xs: List<T>, by: ?(T -> K) = None) -> Heap<T>Build a Heap<T> from xs via Floyd heapify.
by: means what it means in new; without it pops come out in the order of
xs.sorted(), and Heap.of(xs, by: desc) is the O(n) max-heap (MaxHeap.of).
- cost: O(n)
- empty: an empty heap
- traps: never
Examples:
var h = Heap.of([3, 1, 2]); h.pop() == Some(1) and h.len == 2var h = Heap.of([3, 1, 2], by: desc); h.pop() == Some(3)
Heap.len
fn len(self) -> IntNumber of elements currently in the heap.
- cost: O(1)
- traps: never
Examples:
Heap.of([3, 1]).len == 2
Heap.is_empty
fn is_empty(self) -> BoolWhether the heap is empty.
- cost: O(1)
- traps: never
Examples:
Heap.of([3]).is_empty == false
Heap.peek
fn peek(self) -> ?TThe smallest element, or None if the heap is empty.
With by: desc the smallest key is the largest element.
- cost: O(1)
- empty:
None - traps: never
Examples:
Heap.of([3, 1, 2]).peek == Some(1)
Heap.clear
fn clear(mut self)Remove all elements from the heap.
The order by: is kept.
- cost: O(1)
- traps: never
Examples:
var h = Heap.of([1, 2]); h.clear(); h.pop() == None
Heap.take
fn take(mut self) -> Heap<T>Move the heap's contents out in O(1), leaving self empty.
Both heaps keep the order by:.
- cost: O(1)
- traps: never
Examples:
var h = Heap.of([2, 1]); let t = h.take(); h.is_empty and t.peek == Some(1)
Heap.less
fn less(self, a: T, b: T) -> BoolHeap.sift_down
fn sift_down(mut self, start: Int)Heap.push
fn push(mut self, x: T)Push x into the heap.
- cost: O(log n), amortized over list growth
- traps: never
Examples:
var h = Heap.of([5]); h.push(2); h.peek == Some(2)
Heap.pop
fn pop(mut self) -> ?TRemove and return the smallest element, or None if the heap is empty.
- cost: O(log n)
- empty:
None - traps: never
Examples:
var h = Heap.of([2, 1]); h.pop() == Some(1) and h.pop() == Some(2) and h.pop() == None
Heap.reserve
fn reserve(mut self, cap: Int)Reserve backing storage for at least cap elements.
- cost: O(cap) when the storage grows, O(1) otherwise
- traps: never
Examples:
var h = Heap.of([2]); h.reserve(100); h.peek == Some(2)
Heap.push_pop
fn push_pop(mut self, x: T) -> TPush x and pop the minimum in one sift.
Returns x itself, leaving the heap unchanged, when the heap is empty or the key of
x is no greater than the top's; otherwise returns the old top and keeps x.
- cost: O(log n); O(1) when
xis returned - empty: returns
x; the heap stays empty - traps: never
Examples:
var h = Heap.of([2, 5]); h.push_pop(3) == 2 and h.peek == Some(3)var h = Heap.of([2]); h.push_pop(1) == 1 and h.peek == Some(2)
Heap.replace_top
fn replace_top(mut self, x: T) -> ?TReplace the minimum with x and return the old minimum (or None if empty).
The old top is returned even when x is smaller than it. On an empty heap x is
pushed and the result is None.
- cost: O(log n)
- empty: pushes
xand returnsNone - traps: never
Examples:
var h = Heap.of([2, 5]); h.replace_top(9) == Some(2) and h.peek == Some(5)var h: Heap<Int> = Heap(); h.replace_top(4) == None and h.peek == Some(4)
Heap.push_all
fn push_all(mut self, items: List<T>)Push all elements of items.
- cost: O(k log n) for
kitems - empty: an empty
itemsdoes nothing - traps: never
Examples:
var h = Heap.of([4]); h.push_all([3, 1]); h.peek == Some(1) and h.len == 3
Heap.drain
fn drain(mut self) -> yields TPop and yield all elements in ascending order, leaving the heap empty.
Each step is one pop. A loop that stops early leaves the elements not yet yielded in
the heap.
- cost: O(log n) per step
- empty: yields nothing
- order: ascending key order, the order
popwould return them - traps: never
Examples:
var h = Heap.of([3, 1, 2]); h.drain().collect() == [1, 2, 3] and h.is_empty
ErasableHeap
pub struct ErasableHeap<T>Min-heap supporting O(log n) arbitrary-value remove(x) via a lazy deletion heap.
push and remove are O(log n); peek and pop are O(log n) amortized; len, is_empty,
clear, and take are O(1).
ErasableHeap.new
fn new<K>(by: ?(T -> K) = None) -> ErasableHeap<T>Create an empty ErasableHeap<T>, optionally ordered by key extractor by: (W7).
- cost: O(1)
- traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(2); h.push(1); h.remove(1); h.pop() == Some(2)
ErasableHeap.len
fn len(self) -> IntNumber of active elements in the heap.
Pushed elements minus removed ones, counting copies.
- cost: O(1)
- traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(1); h.push(1); h.remove(1); h.len == 1
ErasableHeap.is_empty
fn is_empty(self) -> BoolWhether no active elements remain.
- cost: O(1)
- traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(1); h.remove(1); h.is_empty
ErasableHeap.clear
fn clear(mut self)Remove all elements from the heap.
- cost: O(1)
- traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(1); h.clear(); h.pop() == None
ErasableHeap.take
fn take(mut self) -> ErasableHeap<T>Move the heap's contents out in O(1), leaving self empty.
Pending removals move with the contents.
- cost: O(1)
- traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(1); let t = h.take(); h.is_empty and t.len == 1
ErasableHeap.prune
fn prune(mut self)ErasableHeap.push
fn push(mut self, x: T)Push x into the heap.
- cost: O(log n)
- traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(4); h.peek() == Some(4)
ErasableHeap.remove
fn remove(mut self, x: T)Schedule one copy of x for lazy removal (x must be present).
One copy goes, even when several are present. The copy leaves at once as far as len,
peek and pop can see; its storage is freed when it would reach the top. Removing a
value that is not present corrupts the heap: debug builds trap when they find such a
value surfacing.
- cost: O(log n)
- traps: never in release; debug traps when
xis found not to be present
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(1); h.push(1); h.push(3); h.remove(1); h.pop() == Some(1) and h.pop() == Some(3)
ErasableHeap.peek
fn peek(mut self) -> ?TReturn the smallest active element, or None if empty.
Takes mut self because it first discards removed values sitting on top.
- cost: O(log n) amortized
- empty:
None - traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(1); h.push(2); h.remove(1); h.peek() == Some(2)
ErasableHeap.pop
fn pop(mut self) -> ?TRemove and return the smallest active element, or None if empty.
- cost: O(log n) amortized
- empty:
None - traps: never
Examples:
var h: ErasableHeap<Int> = ErasableHeap(); h.push(5); h.push(2); h.pop() == Some(2) and h.len == 1
IndexedHeap
pub struct IndexedHeap<D, K>Domain-keyed min-heap over D supporting O(log n) set, decrease, increase, remove,
and pop, plus O(1) contains, get, and peek.
Each v: D is in the heap at most once, with one key K. Ties between equal keys go to the
smaller v in D's order, so the pop order is fully determined. Memory is O(|D|).
IndexedHeap.new
fn new() -> IndexedHeap<D, K>Create an empty IndexedHeap<D, K>.
- cost: O(|D|)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.len == 0
IndexedHeap.len
fn len(self) -> IntNumber of keys currently in the heap.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(1), 5); h.set(V(1), 6); h.len == 1
IndexedHeap.is_empty
fn is_empty(self) -> BoolWhether the heap is empty.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.is_empty
IndexedHeap.contains
fn contains(self, v: D) -> BoolWhether v is currently in the heap.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(2), 5); h.contains(V(2)) and not h.contains(V(3))
IndexedHeap.get
fn get(self, v: D) -> ?KCurrent priority of v, or None if absent.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(2), 5); h.get(V(2)) == Some(5) and h.get(V(0)) == None
IndexedHeap.peek
fn peek(self) -> ?(D, K)Pair (v, key) with the smallest key, or None if empty.
- cost: O(1)
- empty:
None - traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(3), 1); h.set(V(1), 1); h.peek == Some((V(1), 1))
IndexedHeap.clear
fn clear(mut self)Remove all entries from the heap.
- cost: O(len)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(1), 5); h.clear(); h.get(V(1)) == None
IndexedHeap.before
fn before(self, a: D, b: D) -> BoolIndexedHeap.swap_at
fn swap_at(mut self, i: Int, j: Int)IndexedHeap.sift_up
fn sift_up(mut self, start: Int)IndexedHeap.sift_down
fn sift_down(mut self, start: Int)IndexedHeap.set
fn set(mut self, v: D, k: K)Insert v with key k, or update v's key to k.
The new key may be larger or smaller than the old one.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(1), 5); h.set(V(1), 9); h.get(V(1)) == Some(9)
IndexedHeap.decrease
fn decrease(mut self, v: D, k: K) -> BoolInsert v with k, or lower its key to k if k is smaller. Returns true if updated.
The relaxation step of Dijkstra. An equal key is not smaller: it returns false.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.decrease(V(1), 5) and not h.decrease(V(1), 5) and h.decrease(V(1), 3) and h.get(V(1)) == Some(3)
IndexedHeap.increase
fn increase(mut self, v: D, k: K) -> BoolInsert v with k, or raise its key to k if k is larger. Returns true if updated.
An equal key is not larger: it returns false.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.increase(V(1), 5) and not h.increase(V(1), 2) and h.get(V(1)) == Some(5)
IndexedHeap.remove
fn remove(mut self, v: D) -> ?KRemove v from the heap if present; returns its old key or None.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(1), 5); h.remove(V(1)) == Some(5) and h.remove(V(1)) == None
IndexedHeap.pop
fn pop(mut self) -> ?(D, K)Remove and return (v, key) with the smallest key, or None if empty.
- cost: O(log n)
- empty:
None - traps: never
Examples:
domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(2), 5); h.set(V(0), 7); h.pop() == Some((V(2), 5)) and h.len == 1domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.set(V(3), 1); h.set(V(1), 1); h.pop() == Some((V(1), 1))
MinMaxHeap
pub struct MinMaxHeap<T>MinMaxHeap.new
fn new<K>(by: ?(T -> K) = None) -> MinMaxHeap<T>Create an empty MinMaxHeap<T>, optionally ordered by key extractor by: (W7).
- cost: O(1)
- traps: never
Examples:
var h: MinMaxHeap<Int> = MinMaxHeap(); h.push(2); h.push(7); h.first == Some(2) and h.last == Some(7)
MinMaxHeap.of
fn of(xs: List<T>) -> MinMaxHeap<T>Build a MinMaxHeap<T> from xs in linear time.
The heap orders the elements themselves (there is no by:).
- cost: O(n)
- empty: an empty heap
- traps: never
Examples:
var h = MinMaxHeap.of([3, 1, 4, 1, 5]); h.pop_last() == Some(5) and h.pop_first() == Some(1) and h.first == Some(1)
MinMaxHeap.reserve
fn reserve(mut self, cap: Int)Reserve backing storage for at least cap elements.
- cost: O(cap) when the storage grows, O(1) otherwise
- traps: never
Examples:
var h = MinMaxHeap.of([2]); h.reserve(100); h.first == Some(2)
MinMaxHeap.len
fn len(self) -> IntNumber of elements currently in the heap.
- cost: O(1)
- traps: never
Examples:
MinMaxHeap.of([1, 1]).len == 2
MinMaxHeap.is_empty
fn is_empty(self) -> BoolWhether the heap is empty.
- cost: O(1)
- traps: never
Examples:
MinMaxHeap.of([1]).is_empty == false
MinMaxHeap.first
fn first(self) -> ?TThe smallest element, or None if empty.
With one element, first and last are the same element.
- cost: O(1)
- empty:
None - ties: unspecified among equal keys under
by:;pop_firstreturns the one shown - traps: never
Examples:
MinMaxHeap.of([3, 1, 2]).first == Some(1)MinMaxHeap.of([7]).first == Some(7)
MinMaxHeap.last
fn last(self) -> ?TThe largest element, or None if empty.
- cost: O(1)
- empty:
None - ties: unspecified among equal keys under
by:;pop_lastreturns the one shown - traps: never
Examples:
MinMaxHeap.of([3, 1, 2]).last == Some(3)MinMaxHeap.of([7]).last == Some(7)
MinMaxHeap.push
fn push(mut self, x: T)Insert x.
- cost: O(log n), amortized over list growth
- traps: never
Examples:
var h = MinMaxHeap.of([2, 5]); h.push(9); h.last == Some(9) and h.first == Some(2)
MinMaxHeap.pop_first
fn pop_first(mut self) -> ?TRemove and return the smallest element, or None if empty.
- cost: O(log n)
- empty:
None - traps: never
Examples:
var h = MinMaxHeap.of([2, 5, 3]); h.pop_first() == Some(2) and h.first == Some(3)
MinMaxHeap.pop_last
fn pop_last(mut self) -> ?TRemove and return the largest element, or None if empty.
- cost: O(log n)
- empty:
None - traps: never
Examples:
var h = MinMaxHeap.of([2, 5, 3]); h.pop_last() == Some(5) and h.last == Some(3)
MinMaxHeap.clear
fn clear(mut self)Remove all elements.
- cost: O(1)
- traps: never
Examples:
var h = MinMaxHeap.of([2]); h.clear(); h.first == None
MinMaxHeap.take
fn take(mut self) -> MinMaxHeap<T>Move contents out in O(1), leaving self empty.
- cost: O(1)
- traps: never
Examples:
var h = MinMaxHeap.of([2]); let t = h.take(); h.is_empty and t.first == Some(2)
MinMaxHeap.less
fn less(self, a: T, b: T) -> BoolMinMaxHeap.swap
fn swap(mut self, i: Int, j: Int)MinMaxHeap.max_at
fn max_at(self) -> IntMinMaxHeap.bubble_up
fn bubble_up(mut self, start: Int, min_side: Bool)MinMaxHeap.remove_at
fn remove_at(mut self, i: Int)MinMaxHeap.trickle_down
fn trickle_down(mut self, start: Int)MeldHeap
pub struct MeldHeap<T>Meldable min-heap (skew / leftist heap) with O(log n) meld and O(1) lazy offset add_all.
peek / top is O(1); push, pop, and meld are O(log n).
MeldHeap.new
fn new<K>(by: ?(T -> K) = None) -> MeldHeap<T>Create an empty MeldHeap<T>, optionally ordered by key extractor by: (W7).
- cost: O(1)
- traps: never
Examples:
var h: MeldHeap<Int> = MeldHeap(); h.push(3); h.push(1); h.pop() == Some(1)
MeldHeap.of
fn of(xs: List<T>) -> MeldHeap<T>Build a MeldHeap<T> from xs.
The heap orders the elements themselves (there is no by:).
- cost: O(n)
- empty: an empty heap
- traps: never
Examples:
MeldHeap.of([4, 2, 3]).peek == Some(2)
MeldHeap.len
fn len(self) -> IntNumber of elements currently in the heap.
- cost: O(1)
- traps: never
Examples:
MeldHeap.of([4, 2]).len == 2
MeldHeap.is_empty
fn is_empty(self) -> BoolWhether the heap is empty.
- cost: O(1)
- traps: never
Examples:
MeldHeap.of([4]).is_empty == false
MeldHeap.peek
fn peek(self) -> ?TThe smallest element, or None if empty.
The value includes every add_all applied since it was pushed.
- cost: O(1)
- empty:
None - traps: never
Examples:
var h = MeldHeap.of([4, 2]); h.add_all(1); h.peek == Some(3)
MeldHeap.top
fn top(self) -> ?TThe smallest element, or None if empty (alias for peek).
see: peek
- cost: O(1)
- empty:
None - ties: as
peek: unspecified among equal keys underby: - traps: never
Examples:
MeldHeap.of([4, 2]).top == Some(2)
MeldHeap.push
fn push(mut self, x: T)Push x into the heap.
x is stored as given: earlier add_all offsets do not apply to it.
- cost: O(log n)
- traps: never
Examples:
var h = MeldHeap.of([1, 5]); h.add_all(10); h.push(3); h.drain() == [3, 11, 15]
MeldHeap.push_all
fn push_all(mut self, items: List<T>)Push all elements of items.
- cost: O(k log n) for
kitems - empty: an empty
itemsdoes nothing - traps: never
Examples:
var h = MeldHeap.of([4]); h.push_all([3, 1]); h.drain() == [1, 3, 4]
MeldHeap.pop
fn pop(mut self) -> ?TRemove and return the smallest element, or None if empty.
- cost: O(log n)
- empty:
None - traps: never
Examples:
var h = MeldHeap.of([4, 2]); h.pop() == Some(2) and h.pop() == Some(4) and h.pop() == None
MeldHeap.meld
fn meld(mut self, other: MeldHeap<T>)Meld other into self (consuming other).
Every element keeps the value its own heap reported: pending add_all offsets apply only
to the elements they were added to.
- cost: O(log n)
- traps: never
Examples:
var a = MeldHeap.of([4, 2]); a.meld(MeldHeap.of([3, 1])); a.drain() == [1, 2, 3, 4]
MeldHeap.absorb
fn absorb(mut self, mut other: MeldHeap<T>)Meld other into self, leaving other empty.
meld for an other you keep using: small-to-large merging over a tree.
- cost: O(log n)
- traps: never
Examples:
var a = MeldHeap.of([4]); var b = MeldHeap.of([1]); a.absorb(mut b); a.peek == Some(1) and b.is_empty
MeldHeap.add_all
fn add_all(mut self, delta: T)Add delta lazily to every element (for additive types).
Only the elements in the heap now change; later pushes do not. Adding one value to
every element keeps their order; with by:, the key must keep that order too, or later
pops are unspecified.
- cost: O(1)
- empty: does nothing
- traps: never (overflow wraps in release, traps in debug)
Examples:
var h = MeldHeap.of([1, 5]); h.add_all(10); h.pop() == Some(11)
MeldHeap.clear
fn clear(mut self)Remove all elements.
- cost: O(1)
- traps: never
Examples:
var h = MeldHeap.of([1]); h.clear(); h.pop() == None
MeldHeap.take
fn take(mut self) -> MeldHeap<T>Move contents out in O(1), leaving self empty.
- cost: O(1)
- traps: never
Examples:
var h = MeldHeap.of([1]); let t = h.take(); h.is_empty and t.peek == Some(1)
MeldHeap.drain
fn drain(mut self) -> List<T>Pop and return all elements in ascending order, leaving self empty.
- cost: O(n log n)
- empty:
[] - order: ascending key order, the order
popwould return them; a newList, keyed from 0 - traps: never
Examples:
var h = MeldHeap.of([3, 1, 2]); h.drain() == [1, 2, 3] and h.is_empty
MeldHeap.less
fn less(self, a: T, b: T) -> BoolMeldHeap.node
fn node(mut self, x: T) -> IntMeldHeap.rank_of
fn rank_of(self, t: Int) -> IntMeldHeap.push_down
fn push_down(mut self, t: Int)MeldHeap.merge
fn merge(mut self, a: Int, b: Int) -> IntMinHeap
pub type MinHeap<T> = Heap<T>Heap<T>(): pops the smallest first.
MaxHeap
pub struct MaxHeap<T>Heap<T>(by: desc) under its own name: pops the largest first, with the same operations and
costs as Heap; it holds each element as desc(x). For a mixed order use Heap with desc(x) in the entry.
MaxHeap.new
fn new() -> MaxHeap<T>An empty MaxHeap<T>.
- cost: O(1)
- traps: never
Examples:
var h = MaxHeap<Int>(); h.push(1); h.push(3); h.pop() == Some(3)
MaxHeap.of
fn of(xs: List<T>) -> MaxHeap<T>Build a MaxHeap<T> from xs via Floyd heapify.
- cost: O(n)
- empty: an empty heap
- traps: never
Examples:
var h = MaxHeap.of([3, 1, 2]); h.pop() == Some(3) and h.len == 2
MaxHeap.len
fn len(self) -> IntNumber of elements currently in the heap.
- cost: O(1)
- traps: never
Examples:
MaxHeap.of([3, 1]).len == 2
MaxHeap.is_empty
fn is_empty(self) -> BoolWhether the heap is empty.
- cost: O(1)
- traps: never
Examples:
MaxHeap.of([3]).is_empty == false
MaxHeap.peek
fn peek(self) -> ?TThe largest element, or None when empty.
- cost: O(1)
- traps: never
Examples:
MaxHeap.of([3, 9, 2]).peek == Some(9)
MaxHeap.clear
fn clear(mut self)Remove every element.
- cost: O(1)
- traps: never
Examples:
var h = MaxHeap.of([2]); h.clear(); h.is_empty
MaxHeap.take
fn take(mut self) -> MaxHeap<T>Move the contents out, leaving this heap empty.
- cost: O(1)
- traps: never
Examples:
var h = MaxHeap.of([2, 7]); let t = h.take(); h.is_empty and t.peek == Some(7)
MaxHeap.push
fn push(mut self, x: T)Add x.
- cost: O(log n)
- traps: never
Examples:
var h = MaxHeap.of([2]); h.push(5); h.peek == Some(5)
MaxHeap.pop
fn pop(mut self) -> ?TRemove and return the largest element, or None when empty.
- cost: O(log n)
- traps: never
Examples:
var h = MaxHeap.of([4, 9]); h.pop() == Some(9) and h.pop() == Some(4) and h.pop() == None
MaxHeap.reserve
fn reserve(mut self, cap: Int)Make room for cap elements in total.
- cost: O(cap) when the storage grows, O(1) otherwise
- traps: never
Examples:
var h = MaxHeap.of([2]); h.reserve(100); h.peek == Some(2)
MaxHeap.push_pop
fn push_pop(mut self, x: T) -> TPush x, then pop and return the largest element.
- cost: O(log n); O(1) when
xis returned - traps: never
Examples:
var h = MaxHeap.of([4]); h.push_pop(7) == 7 and h.peek == Some(4)
MaxHeap.replace_top
fn replace_top(mut self, x: T) -> ?TPop the largest element, then push x; returns the popped one, or None
(and only pushes) when empty.
- cost: O(log n)
- traps: never
Examples:
var h = MaxHeap.of([4]); h.replace_top(1) == Some(4) and h.peek == Some(1)var h = MaxHeap<Int>(); h.replace_top(4) == None and h.peek == Some(4)
MaxHeap.push_all
fn push_all(mut self, items: List<T>)Push every element of items.
- cost: O(n + k log(n + k))
- empty: changes nothing
- traps: never
Examples:
var h = MaxHeap<Int>(); h.push_all([3, 8]); h.peek == Some(8)
MaxHeap.drain
fn drain(mut self) -> yields TPop every element, largest first.
- cost: O(n log n)
- empty: yields nothing
- traps: never
Examples:
var h = MaxHeap.of([1, 3, 2]); h.drain().collect() == [3, 2, 1]
Settle
pub struct Settle<K, P>(best: (P, P) -> P = min)A keyed frontier where each key pops exactly once. offer(k, p) keeps the best priority seen
for a key that has not popped yet and is ignored after it has; pop returns the best key
and settles it. The shape of Dijkstra, Prim and "settle answers from the largest down",
without a side array of done flags or a lazy-deletion continue. O(log n) per offer and pop.
best picks the better of two priorities and must return one of its arguments, like min
and max; with any other function the popped priorities are unspecified. Keys are hashed.
Settle.better
fn better(self, a: Int, b: Int) -> BoolSettle.sift_up
fn sift_up(mut self, i0: Int)Settle.sift_down
fn sift_down(mut self)Settle.offer
fn offer(mut self, k: K, p: P)Offer priority p for key k: an unsettled key keeps best(old, p) (or p when it
had None); a settled key ignores the offer.
- cost: O(log n) amortized,
nthe offers so far - traps: never
Examples:
var s: Settle<Char, Int> = Settle(); s.offer('a', 5); s.offer('a', 2); s.offer('a', 4); s.get('a') == Some(2)
Settle.pop
fn pop(mut self) -> ?(K, P)Settle and return the unsettled key whose priority is best, with that priority, or
None when every offered key has settled.
- cost: O(log n) amortized,
nthe offers so far - empty:
None - ties: unspecified among keys with equal priorities, as in
Heap - traps: never
Examples:
var s: Settle<Char, Int> = Settle(); s.offer('a', 5); s.offer('b', 3); s.pop() == Some(('b', 3)) and s.settled('b')var s: Settle<Char, Int> = Settle(); s.offer('b', 3); s.pop(); s.offer('b', 1); s.pop() == Nonevar s: Settle<Char, Int> = Settle(best: max); s.offer('a', 5); s.offer('b', 3); s.pop() == Some(('a', 5))
Settle.settled
fn settled(self, k: K) -> BoolWhether k has popped.
- cost: O(1) expected
- traps: never
Examples:
var s: Settle<Char, Int> = Settle(); s.offer('a', 1); not s.settled('a') and s.pop() == Some(('a', 1)) and s.settled('a')
Settle.get
fn get(self, k: K) -> ?PThe best priority offered for k so far (for a settled key, the one it popped with),
or None if k was never offered.
- cost: O(1) expected
- traps: never
Examples:
var s: Settle<Char, Int> = Settle(); s.offer('a', 4); s.get('a') == Some(4) and s.get('b') == None