Struct crater::mmheap::MmHeap

pub struct MmHeap<T> { /* private fields */ }

An implicit binary heap that can efficiently find the min or max of its contained elements.

• Find min / find max: O(1)
• Pop min / pop max: O(log(n))
• Push: O(log(n))
• Heapify: O(n) The comparison function can be changed after creation by just calling MmHeap::ify_by again. Rust’s standard std::collections::BinaryHeap claims an O(1) average complexity for push, but as it notes in the documentation this is amortized over a randomly ordered sequence. This heap is also a binary heap so for a randomly ordered sequence it could also be considered O(1), but for this, the standard binary heap, and indeed any binary heap, the worst case insertion time is O(logn). Also, when a min (or minmax) heap is used to find the m largest elements in a large sequence of n > m elements or visa versa, the expected cost of insertion drops from 1 - m/2^m to … even lower.

Implementations

impl<T> MmHeap<T>

pub fn new() -> Self

Create an empty MmHeap

pub fn make(buf: Vec<T>, cmp: &impl Fn(&T, &T) -> Ordering) -> Self

Create an MmHeap out of a vector and immediately heapify it according to cmp Note that cmp takes references, which means the common case of storing references in the heap can require wrapping the comparison function since it will have to take references to references

pub fn ify_by(&mut self, cmp: &impl Fn(&T, &T) -> Ordering)

Reorder the heap according to a new comparison function. It’s impossible to add to the heap’s private buffer directly, so this is only necessary when changing the comparison function. When calling Self::push_by etc with the same comparison function, the heap will maintain its invariant

pub fn len(&self) -> usize

Get the number of elements in the heap

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

Get the minimum element without removing it

pub fn peek_max_by(&self, cmp: &impl Fn(&T, &T) -> Ordering) -> Option<&T>

Get the maximum element without removing it

pub fn push_by(&mut self, e: T, cmp: &impl Fn(&T, &T) -> Ordering)

Insert an element into the heap Elements that compare equal are fine, but their order will be unspecified

pub fn pop_min_by(&mut self, cmp: &impl Fn(&T, &T) -> Ordering) -> Option<T>

Get the minimal element and remove it

pub fn pop_max_by(&mut self, cmp: &impl Fn(&T, &T) -> Ordering) -> Option<T>

Get the maximal element and remove it

pub fn pushpop_min_by(&mut self, e: T, cmp: &impl Fn(&T, &T) -> Ordering) -> T

Insert a new element and remove the min element in the resulting heap in a single operation Could be faster than Self::push_by + [Self::pop_min_by`] separately (the current implementation is only more efficient if the heap is empty, but it will always be at least as good)

pub fn pushpop_max_by(&mut self, e: T, cmp: &impl Fn(&T, &T) -> Ordering) -> T

Insert a new element and remove the max element in the resulting heap in a single operation

pub fn extend_by<U: IntoIterator<Item = T>>( &mut self, iter: U, cmp: &impl Fn(&T, &T) -> Ordering )

Add all elements yielded from an iterator This is the same functionality provided by the Extend trait, except we need an additional argument (cmp) so we cannot implement that trait

Trait Implementations

impl<T> Into<Vec<T>> for MmHeap<T>

fn into(self) -> Vec<T>

Converts this type into the (usually inferred) input type.

impl<'a, T> IntoIterator for &'a MmHeap<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = <&'a Vec<T> as IntoIterator>::IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.