Struct coca::binary_heap::BinaryHeap

pub struct BinaryHeap<E, B, I = usize> where
    E: Ord,
    B: ContiguousStorage<E>,
    I: Capacity,  { /* fields omitted */ }

A fixed-capacity priority queue implemented with a binary heap.

This will be a max-heap, i.e. heap.pop() will return the largest value in the queue. core::cmp::Reverse or a custom Ord implementation can be used to make a min-heap instead.

It is a logic error for an item to be modified in such a way that the item's ordering relative to any other item, as determined by the Ord trait, changes while it is in the heap. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

Implementations

impl<E, B, I> BinaryHeap<E, B, I> where
    E: Ord,
    B: ContiguousStorage<E>,
    I: Capacity, 

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

Returns a reference to the greatest item in the binary heap, or None if it is empty.

pub fn peek_mut(&mut self) -> Option<PeekMut<'_, E, B, I>>

Returns a mutable reference to the greatest item in the binary heap, or None if it is empty.

Note: If the PeekMut value is leaked, the heap may be left in an inconsistent state.

Examples

let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
let mut heap = coca::SliceHeap::<_>::from(&mut backing_region[..]);
heap.try_push(3);
heap.try_push(5);
heap.try_push(1);

{
    let mut val = heap.peek_mut().unwrap();
    *val = 0;
}

assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), Some(0));

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

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

Examples

use coca::{SliceHeap, SliceVec};
let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
let mut vec = SliceVec::<u32>::from(&mut backing_region[..]);
vec.push(1); vec.push(3);

let mut heap = SliceHeap::from(vec);

assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);

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

Pushes an item onto the binary heap.

Panics

Panics if the heap is already at capacity. See try_push for a checked version that never panics.

pub fn try_push(&mut self, item: E) -> Result<(), E>

Pushes an item onto the binary heap, returning Err(item) if it is full.

Examples

let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
let mut heap = coca::SliceHeap::<_>::from(&mut backing_region[..]);
heap.try_push(3);
heap.try_push(5);
heap.try_push(1);

assert_eq!(heap.len(), 3);
assert_eq!(heap.peek(), Some(&5));

pub fn capacity(&self) -> usize

Returns the number of elements the binary heap can hold.

pub fn len(&self) -> usize

Returns the number of elements in the binary heap, also referred to as its 'length'.

pub fn is_empty(&self) -> bool

Returns true if the binary heap contains no elements.

pub fn is_full(&self) -> bool

Returns true if the binary heap contains the maximum number of elements.

pub fn iter(&self) -> impl Iterator<Item = &E>

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

pub fn drain(&mut self) -> Drain<'_, E, B, I>

Clears the binary heap, returning an iterator over the removed elements. The elements are removed in arbitrary order.

Examples

let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
let mut heap = coca::SliceHeap::<_>::from(&mut backing_region[..]);
heap.push(1); heap.push(3);
assert!(!heap.is_empty());

let mut iter = heap.drain();
assert!(iter.next().is_some());
assert!(iter.next().is_some());
assert!(iter.next().is_none());
drop(iter);

assert!(heap.is_empty());

pub fn drain_sorted(&mut self) -> DrainSorted<'_, E, B, I>

Returns an iterator which retrieves elements in heap order. The retrieved elements are removed from the original heap. The remaining elements will be removed on drop in heap order.

Remarks

.drain_sorted() is O(n * log(n)), much slower than .drain(). The latter is preferable in most cases.

Examples

let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
let mut heap = coca::SliceHeap::<_>::from(&mut backing_region[..]);
heap.push(1); heap.push(3); heap.push(5);

let mut iter = heap.drain_sorted();
assert_eq!(iter.next(), Some(5));
drop(iter);
assert!(heap.is_empty());

pub fn clear(&mut self)

Drops all items from the binary heap.

pub fn into_vec(self) -> Vec<E, B, I>

Consumes the BinaryHeap and returns the underlying vector in arbitrary order.

pub fn into_sorted_vec(self) -> Vec<E, B, I>

Consumes the BinaryHeap and returns a vector in sorted (ascending) order.

Examples

let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 5];
let mut heap = coca::SliceHeap::<_>::from(&mut backing_region[..]);
heap.push(1); heap.push(5); heap.push(3); heap.push(2); heap.push(4);
let vec = heap.into_sorted_vec();
assert_eq!(vec, &[1, 2, 3, 4, 5][..]);

pub fn into_iter_sorted(self) -> IntoIterSorted<E, B, I>

Consumes the BinaryHeap and returns an iterator which yields elements in heap order.

When dropped, the remaining elements will be dropped in heap order.

Remarks

.into_iter_sorted() is O(n * log(n)), much slower than .into_iter(). The latter is preferable in most cases.

Examples

let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
let mut heap = coca::SliceHeap::<_>::from(&mut backing_region[..]);
heap.push(1); heap.push(3); heap.push(5);

let mut iter = heap.into_iter_sorted();
assert_eq!(iter.next(), Some(5));
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), Some(1));

impl<E, I> BinaryHeap<E, Box<[MaybeUninit<E>], Global>, I> where
    E: Copy + Ord,
    I: Capacity, 

pub fn with_capacity(capacity: I) -> Self

This is supported on crate feature alloc only.

Constructs a new, empty AllocHeap<E, I> with the specified capacity.

Panics

Panics if the specified capacity cannot be represented by a usize.

impl<E, I, const C: usize> BinaryHeap<E, [MaybeUninit<E>; C], I> where
    E: Ord,
    I: Capacity, 

pub fn new() -> Self

This is supported on crate feature nightly only.

Constructs a new, empty BinaryHeap backed by an inline array.

Panics

Panics if C cannot be represented as a value of type I.

Examples

let heap = coca::ArrayHeap::<char, 4>::new();
assert_eq!(heap.capacity(), 4);
assert!(heap.is_empty());

Trait Implementations

impl<E, I, const C: usize> Clone for BinaryHeap<E, [MaybeUninit<E>; C], I> where
    E: Clone + Ord,
    I: Capacity, 

This is supported on crate feature nightly only.

pub fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<E, B, I> Debug for BinaryHeap<E, B, I> where
    E: Ord + Debug,
    B: ContiguousStorage<E>,
    I: Capacity, 

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

Formats the value using the given formatter.

impl<E, I, const C: usize> Default for BinaryHeap<E, [MaybeUninit<E>; C], I> where
    E: Ord,
    I: Capacity, 

This is supported on crate feature nightly only.

pub fn default() -> Self

Returns the "default value" for a type.

impl<E1, E2, B, I> Extend<E1> for BinaryHeap<E2, B, I> where
    Vec<E2, B, I>: Extend<E1>,
    E2: Ord,
    B: ContiguousStorage<E2>,
    I: Capacity, 

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

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

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

Extends a collection with exactly one element.

pub 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<E, B, I> From<B> for BinaryHeap<E, B, I> where
    E: Ord,
    B: ContiguousStorage<E>,
    I: Capacity, 

pub fn from(buf: B) -> Self

Converts a contiguous block of memory into an empty binary heap.

Panics

This may panic if the index type I cannot represent buf.capacity().

impl<E, B, I> From<Vec<E, B, I>> for BinaryHeap<E, B, I> where
    E: Ord,
    B: ContiguousStorage<E>,
    I: Capacity, 

pub fn from(vec: Vec<E, B, I>) -> Self

Converts a Vec into a binary heap.

This conversion happens in-place, and has O(n) time complexity.

impl<E, B, I> FromIterator<E> for BinaryHeap<E, B, I> where
    Vec<E, B, I>: FromIterator<E>,
    E: Ord,
    B: ContiguousStorage<E>,
    I: Capacity, 

pub fn from_iter<It: IntoIterator<Item = E>>(iter: It) -> Self

Creates a binary heap from an iterator.

Panics

Panics if the iterator yields more elements than the binary heap can hold.

impl<E, B, I> IntoIterator for BinaryHeap<E, B, I> where
    E: Ord,
    B: ContiguousStorage<E>,
    I: Capacity, 

type Item = E

The type of the elements being iterated over.

type IntoIter = <Vec<E, B, I> as IntoIterator>::IntoIter

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.