Struct SmallBinaryHeap 

pub struct SmallBinaryHeap<T: Ord, const N: usize, K: Kind + HeapKind<T> = Max> { /* private fields */ }

A priority queue that lives on the stack for N items, then spills to the heap.

Behavior

• Heap Kind: Supports both Max (default) and Min heap behavior.
• Spill: Occurs automatically when pushing the (N+1)th item.
• Complexity: Push and Pop are O(log n). Spill is O(n).

Safety Invariants

• on_stack tag determines which side of the HeapData union is active.
• Elements are stored in a binary heap order (array representation).

Implementations

impl<T, const N: usize, K> SmallBinaryHeap<T, N, K>

where T: Ord, K: Kind + HeapKind<T>,

pub const MAX_STACK_SIZE: usize

The maximum allowed stack size in bytes (16 KB).

pub fn new() -> Self

Creates a new empty binary heap.

pub fn with_capacity(capacity: usize) -> Self

Creates a new empty binary heap with a specific initial capacity on the heap. This immediately forces the storage to be on the heap, bypassing the stack optimization.

pub fn is_on_stack(&self) -> bool

Returns true if the heap is currently storing data on the stack.

pub fn len(&self) -> usize

Returns the number of elements in the heap.

pub fn is_empty(&self) -> bool

Returns true if the heap contains no elements.

pub fn capacity(&self) -> usize

Returns the total capacity of the heap. If on stack, returns N. If on heap, returns the vector capacity.

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted. May trigger a spill to heap if current stack capacity is insufficient.

pub fn shrink_to_fit(&mut self)

Discards as much additional capacity as possible.

pub fn peek(&self) -> Option<&T>

Returns a reference to the greatest item.

pub fn peek_mut(&mut self) -> Option<SmallPeekMut<'_, T, N, K>>

Returns a mutable reference to the greatest item.

pub fn push(&mut self, item: T)

Pushes an item onto the binary heap.

If the stack capacity N is exceeded, this triggers a transparent spill to the heap.

pub fn pop(&mut self) -> Option<T>

Removes the greatest item from the binary heap and returns it, or None if it is empty.

pub fn clear(&mut self)

Drops all items from the binary heap.

pub fn append(&mut self, other: &mut Self)

Moves all the elements of other into self, leaving other empty.

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&T) -> bool,

Retains only the elements specified by the predicate. Rebuilds the heap, complexity O(n).

pub fn into_vec(self) -> Vec<T>

Consumes the heap and returns the underlying vector in arbitrary (heap) order.

pub fn into_sorted_vec(self) -> Vec<T>

Consumes the heap and returns a vector sorted from greatest to lowest.

impl<T, const N: usize, K> SmallBinaryHeap<T, N, K>

where T: Ord, K: Kind + HeapKind<T>,

pub fn iter(&self) -> SmallHeapIter<'_, T, K>

Returns an iterator visiting all values in the underlying vector, in arbitrary order.

Trait Implementations

impl<T: Ord, const N: usize, K: Kind + HeapKind<T>> AnyHeap<T> for SmallBinaryHeap<T, N, K>

fn len(&self) -> usize

Returns the number of elements in the heap.

fn push(&mut self, item: T)

Pushes an item onto the heap.

fn pop(&mut self) -> Option<T>

Removes the greatest (or smallest, depending on the heap type) item from the heap and returns it.

fn peek(&self) -> Option<&T>

Returns a reference to the greatest (or smallest) item in the heap.

fn clear(&mut self)

Clears the heap, removing all values.

fn is_empty(&self) -> bool

Returns true if the heap is empty.

impl<T, const N: usize, K> Clone for SmallBinaryHeap<T, N, K>

where T: Ord + Clone, K: Kind + HeapKind<T>, K::Element: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, const N: usize, K> Debug for SmallBinaryHeap<T, N, K>

where T: Ord + Debug, K: Kind + HeapKind<T>,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord, const N: usize, K: Kind + HeapKind<T>> Default for SmallBinaryHeap<T, N, K>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Ord, const N: usize, K: Kind + HeapKind<T>> Drop for SmallBinaryHeap<T, N, K>

fn drop(&mut self)

Executes the destructor for this type.

impl<T, const N: usize, K> Extend<T> for SmallBinaryHeap<T, N, K>

where T: Ord, K: Kind + HeapKind<T>,

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, const N: usize, K> FromIterator<T> for SmallBinaryHeap<T, N, K>

where T: Ord, K: Kind + HeapKind<T>,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, T, const N: usize, K> IntoIterator for &'a SmallBinaryHeap<T, N, K>

where T: Ord, K: Kind + HeapKind<T>,

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = SmallHeapIter<'a, T, K>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const N: usize, K> IntoIterator for SmallBinaryHeap<T, N, K>

where T: Ord, K: Kind + HeapKind<T>,

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, N, K>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.