Skip to Content
ReferenceLibrary

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.

Source

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)

Source

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 == 2
  • var h = Heap.of([3, 1, 2], by: desc); h.pop() == Some(3)

Source

Heap.len

fn len(self) -> Int

Number of elements currently in the heap.

  • cost: O(1)
  • traps: never

Examples:

  • Heap.of([3, 1]).len == 2

Source

Heap.is_empty

fn is_empty(self) -> Bool

Whether the heap is empty.

  • cost: O(1)
  • traps: never

Examples:

  • Heap.of([3]).is_empty == false

Source

Heap.peek

fn peek(self) -> ?T

The 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)

Source

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

Source

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)

Source

Heap.less

fn less(self, a: T, b: T) -> Bool

Source

Heap.sift_down

fn sift_down(mut self, start: Int)

Source

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)

Source

Heap.pop

fn pop(mut self) -> ?T

Remove 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

Source

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)

Source

Heap.push_pop

fn push_pop(mut self, x: T) -> T

Push 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 x is 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)

Source

Heap.replace_top

fn replace_top(mut self, x: T) -> ?T

Replace 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 x and returns None
  • 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)

Source

Heap.push_all

fn push_all(mut self, items: List<T>)

Push all elements of items.

  • cost: O(k log n) for k items
  • empty: an empty items does nothing
  • traps: never

Examples:

  • var h = Heap.of([4]); h.push_all([3, 1]); h.peek == Some(1) and h.len == 3

Source

Heap.drain

fn drain(mut self) -> yields T

Pop 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 pop would return them
  • traps: never

Examples:

  • var h = Heap.of([3, 1, 2]); h.drain().collect() == [1, 2, 3] and h.is_empty

Source

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).

Source

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)

Source

ErasableHeap.len

fn len(self) -> Int

Number 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

Source

ErasableHeap.is_empty

fn is_empty(self) -> Bool

Whether no active elements remain.

  • cost: O(1)
  • traps: never

Examples:

  • var h: ErasableHeap<Int> = ErasableHeap(); h.push(1); h.remove(1); h.is_empty

Source

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

Source

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

Source

ErasableHeap.prune

fn prune(mut self)

Source

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)

Source

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 x is 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)

Source

ErasableHeap.peek

fn peek(mut self) -> ?T

Return 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)

Source

ErasableHeap.pop

fn pop(mut self) -> ?T

Remove 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

Source

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|).

Source

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

Source

IndexedHeap.len

fn len(self) -> Int

Number 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

Source

IndexedHeap.is_empty

fn is_empty(self) -> Bool

Whether the heap is empty.

  • cost: O(1)
  • traps: never

Examples:

  • domain V = 0..4; var h: IndexedHeap<V, Int> = IndexedHeap(); h.is_empty

Source

IndexedHeap.contains

fn contains(self, v: D) -> Bool

Whether 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))

Source

IndexedHeap.get

fn get(self, v: D) -> ?K

Current 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

Source

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))

Source

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

Source

IndexedHeap.before

fn before(self, a: D, b: D) -> Bool

Source

IndexedHeap.swap_at

fn swap_at(mut self, i: Int, j: Int)

Source

IndexedHeap.sift_up

fn sift_up(mut self, start: Int)

Source

IndexedHeap.sift_down

fn sift_down(mut self, start: Int)

Source

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)

Source

IndexedHeap.decrease

fn decrease(mut self, v: D, k: K) -> Bool

Insert 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)

Source

IndexedHeap.increase

fn increase(mut self, v: D, k: K) -> Bool

Insert 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)

Source

IndexedHeap.remove

fn remove(mut self, v: D) -> ?K

Remove 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

Source

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 == 1
  • domain 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))

Source

MinMaxHeap

pub struct MinMaxHeap<T>

Source

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)

Source

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)

Source

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)

Source

MinMaxHeap.len

fn len(self) -> Int

Number of elements currently in the heap.

  • cost: O(1)
  • traps: never

Examples:

  • MinMaxHeap.of([1, 1]).len == 2

Source

MinMaxHeap.is_empty

fn is_empty(self) -> Bool

Whether the heap is empty.

  • cost: O(1)
  • traps: never

Examples:

  • MinMaxHeap.of([1]).is_empty == false

Source

MinMaxHeap.first

fn first(self) -> ?T

The 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_first returns the one shown
  • traps: never

Examples:

  • MinMaxHeap.of([3, 1, 2]).first == Some(1)
  • MinMaxHeap.of([7]).first == Some(7)

Source

MinMaxHeap.last

fn last(self) -> ?T

The largest element, or None if empty.

  • cost: O(1)
  • empty: None
  • ties: unspecified among equal keys under by:; pop_last returns the one shown
  • traps: never

Examples:

  • MinMaxHeap.of([3, 1, 2]).last == Some(3)
  • MinMaxHeap.of([7]).last == Some(7)

Source

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)

Source

MinMaxHeap.pop_first

fn pop_first(mut self) -> ?T

Remove 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)

Source

MinMaxHeap.pop_last

fn pop_last(mut self) -> ?T

Remove 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)

Source

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

Source

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)

Source

MinMaxHeap.less

fn less(self, a: T, b: T) -> Bool

Source

MinMaxHeap.swap

fn swap(mut self, i: Int, j: Int)

Source

MinMaxHeap.max_at

fn max_at(self) -> Int

Source

MinMaxHeap.bubble_up

fn bubble_up(mut self, start: Int, min_side: Bool)

Source

MinMaxHeap.remove_at

fn remove_at(mut self, i: Int)

Source

MinMaxHeap.trickle_down

fn trickle_down(mut self, start: Int)

Source

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).

Source

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)

Source

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)

Source

MeldHeap.len

fn len(self) -> Int

Number of elements currently in the heap.

  • cost: O(1)
  • traps: never

Examples:

  • MeldHeap.of([4, 2]).len == 2

Source

MeldHeap.is_empty

fn is_empty(self) -> Bool

Whether the heap is empty.

  • cost: O(1)
  • traps: never

Examples:

  • MeldHeap.of([4]).is_empty == false

Source

MeldHeap.peek

fn peek(self) -> ?T

The 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)

Source

MeldHeap.top

fn top(self) -> ?T

The smallest element, or None if empty (alias for peek).

see: peek

  • cost: O(1)
  • empty: None
  • ties: as peek: unspecified among equal keys under by:
  • traps: never

Examples:

  • MeldHeap.of([4, 2]).top == Some(2)

Source

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]

Source

MeldHeap.push_all

fn push_all(mut self, items: List<T>)

Push all elements of items.

  • cost: O(k log n) for k items
  • empty: an empty items does nothing
  • traps: never

Examples:

  • var h = MeldHeap.of([4]); h.push_all([3, 1]); h.drain() == [1, 3, 4]

Source

MeldHeap.pop

fn pop(mut self) -> ?T

Remove 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

Source

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]

Source

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

Source

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)

Source

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

Source

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)

Source

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 pop would return them; a new List, keyed from 0
  • traps: never

Examples:

  • var h = MeldHeap.of([3, 1, 2]); h.drain() == [1, 2, 3] and h.is_empty

Source

MeldHeap.less

fn less(self, a: T, b: T) -> Bool

Source

MeldHeap.node

fn node(mut self, x: T) -> Int

Source

MeldHeap.rank_of

fn rank_of(self, t: Int) -> Int

Source

MeldHeap.push_down

fn push_down(mut self, t: Int)

Source

MeldHeap.merge

fn merge(mut self, a: Int, b: Int) -> Int

Source

MinHeap

pub type MinHeap<T> = Heap<T>

Heap<T>(): pops the smallest first.

Source

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.

Source

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)

Source

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

Source

MaxHeap.len

fn len(self) -> Int

Number of elements currently in the heap.

  • cost: O(1)
  • traps: never

Examples:

  • MaxHeap.of([3, 1]).len == 2

Source

MaxHeap.is_empty

fn is_empty(self) -> Bool

Whether the heap is empty.

  • cost: O(1)
  • traps: never

Examples:

  • MaxHeap.of([3]).is_empty == false

Source

MaxHeap.peek

fn peek(self) -> ?T

The largest element, or None when empty.

  • cost: O(1)
  • traps: never

Examples:

  • MaxHeap.of([3, 9, 2]).peek == Some(9)

Source

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

Source

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)

Source

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)

Source

MaxHeap.pop

fn pop(mut self) -> ?T

Remove 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

Source

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)

Source

MaxHeap.push_pop

fn push_pop(mut self, x: T) -> T

Push x, then pop and return the largest element.

  • cost: O(log n); O(1) when x is returned
  • traps: never

Examples:

  • var h = MaxHeap.of([4]); h.push_pop(7) == 7 and h.peek == Some(4)

Source

MaxHeap.replace_top

fn replace_top(mut self, x: T) -> ?T

Pop 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)

Source

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)

Source

MaxHeap.drain

fn drain(mut self) -> yields T

Pop 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]

Source

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.

Source

Settle.better

fn better(self, a: Int, b: Int) -> Bool

Source

Settle.sift_up

fn sift_up(mut self, i0: Int)

Source

Settle.sift_down

fn sift_down(mut self)

Source

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, n the 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)

Source

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, n the 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() == None
  • var s: Settle<Char, Int> = Settle(best: max); s.offer('a', 5); s.offer('b', 3); s.pop() == Some(('a', 5))

Source

Settle.settled

fn settled(self, k: K) -> Bool

Whether 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')

Source

Settle.get

fn get(self, k: K) -> ?P

The 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

Source

On this page

HeapHeap.newHeap.ofHeap.lenHeap.is_emptyHeap.peekHeap.clearHeap.takeHeap.lessHeap.sift_downHeap.pushHeap.popHeap.reserveHeap.push_popHeap.replace_topHeap.push_allHeap.drainErasableHeapErasableHeap.newErasableHeap.lenErasableHeap.is_emptyErasableHeap.clearErasableHeap.takeErasableHeap.pruneErasableHeap.pushErasableHeap.removeErasableHeap.peekErasableHeap.popIndexedHeapIndexedHeap.newIndexedHeap.lenIndexedHeap.is_emptyIndexedHeap.containsIndexedHeap.getIndexedHeap.peekIndexedHeap.clearIndexedHeap.beforeIndexedHeap.swap_atIndexedHeap.sift_upIndexedHeap.sift_downIndexedHeap.setIndexedHeap.decreaseIndexedHeap.increaseIndexedHeap.removeIndexedHeap.popMinMaxHeapMinMaxHeap.newMinMaxHeap.ofMinMaxHeap.reserveMinMaxHeap.lenMinMaxHeap.is_emptyMinMaxHeap.firstMinMaxHeap.lastMinMaxHeap.pushMinMaxHeap.pop_firstMinMaxHeap.pop_lastMinMaxHeap.clearMinMaxHeap.takeMinMaxHeap.lessMinMaxHeap.swapMinMaxHeap.max_atMinMaxHeap.bubble_upMinMaxHeap.remove_atMinMaxHeap.trickle_downMeldHeapMeldHeap.newMeldHeap.ofMeldHeap.lenMeldHeap.is_emptyMeldHeap.peekMeldHeap.topMeldHeap.pushMeldHeap.push_allMeldHeap.popMeldHeap.meldMeldHeap.absorbMeldHeap.add_allMeldHeap.clearMeldHeap.takeMeldHeap.drainMeldHeap.lessMeldHeap.nodeMeldHeap.rank_ofMeldHeap.push_downMeldHeap.mergeMinHeapMaxHeapMaxHeap.newMaxHeap.ofMaxHeap.lenMaxHeap.is_emptyMaxHeap.peekMaxHeap.clearMaxHeap.takeMaxHeap.pushMaxHeap.popMaxHeap.reserveMaxHeap.push_popMaxHeap.replace_topMaxHeap.push_allMaxHeap.drainSettleSettle.betterSettle.sift_upSettle.sift_downSettle.offerSettle.popSettle.settledSettle.get