Struct MinMaxHeap

pub struct MinMaxHeap<T>(/* private fields */);

A double-ended priority queue.

Most operations are O(log n).

Implementations

impl<T> MinMaxHeap<T>

pub fn new() -> Self

Creates a new, empty MinMaxHeap.

O(1).

pub fn with_capacity(len: usize) -> Self

Creates a new, empty MinMaxHeap with space allocated to hold len elements.

O(n).

pub fn len(&self) -> usize

The number of elements in the heap.

O(1).

pub fn is_empty(&self) -> bool

Is the heap empty?

O(1).

impl<T: Ord> MinMaxHeap<T>

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

Adds an element to the heap.

Amortized O(log n); worst-case O(n) when the backing vector needs to grow.

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

Gets a reference to the minimum element, if any.

O(1).

pub fn peek_min_mut(&mut self) -> Option<PeekMinMut<'_, T>>

Returns a mutable reference to the minimum element, if any. Once this reference is dropped, the heap is adjusted if necessary.

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

O(1) for the peek; O(log n) when the reference is dropped.

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

Gets a reference to the maximum element, if any.

O(1).

pub fn peek_max_mut(&mut self) -> Option<PeekMaxMut<'_, T>>

Returns a mutable reference to the maximum element, if any. Once this reference is dropped, the heap is adjusted if necessary.

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

O(1) for the peek; O(log n) when the reference is dropped.

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

Removes the minimum element, if any.

O(log n).

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

Removes the maximum element, if any.

O(log n).

pub fn push_pop_min(&mut self, element: T) -> T

Pushes an element, then pops the minimum element.

Unlike a push followed by a pop, this combined operation will not allocate.

O(log n).

pub fn push_pop_max(&mut self, element: T) -> T

Pushes an element, then pops the maximum element in an optimized fashion.

Unlike a push followed by a pop, this combined operation will not allocate.

O(log n).

pub fn replace_min(&mut self, element: T) -> Option<T>

Pops the minimum, then pushes an element in an optimized fashion.

O(log n).

pub fn replace_max(&mut self, element: T) -> Option<T>

Pops the maximum, then pushes an element in an optimized fashion.

O(log n).

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

Returns an ascending (sorted) vector, reusing the heap’s storage.

O(n log n).

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

Returns an descending (sorted) vector, reusing the heap’s storage.

O(n log n).

impl<T> MinMaxHeap<T>

pub fn clear(&mut self)

Drops all items from the heap.

O(n)

pub fn capacity(&self) -> usize

The number of elements the heap can hold without reallocating.

O(1)

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

Reserves the minimum capacity for exactly additional more elements to be inserted in the given MinMaxHeap.

O(n)

Panics

Panics if the new capacity overflows usize.

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

Reserves the minimum capacity for at least additional more elements to be inserted in the given MinMaxHeap.

O(n)

Panics

Panics if the new capacity overflows usize.

pub fn shrink_to_fit(&mut self)

Discards extra capacity.

O(n)

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

Consumes the MinMaxHeap and returns its elements in a vector in arbitrary order.

O(n)

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

Returns a borrowing iterator over the min-max-heap’s elements in arbitrary order.

O(1) on creation, and O(1) for each next() operation.

pub fn drain(&mut self) -> Drain<'_, T>

Returns a draining iterator over the min-max-heap’s elements in arbitrary order.

O(1) on creation, and O(1) for each next() operation.

pub fn drain_asc(&mut self) -> DrainAsc<'_, T>

Returns a draining iterator over the min-max-heap’s elements in ascending (min-first) order.

O(1) on creation, and O(log n) for each next() operation.

pub fn drain_desc(&mut self) -> DrainDesc<'_, T>

Returns a draining iterator over the min-max-heap’s elements in descending (max-first) order.

O(1) on creation, and O(log n) for each next() operation.

Trait Implementations

impl<T: Clone> Clone for MinMaxHeap<T>

fn clone(&self) -> MinMaxHeap<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for MinMaxHeap<T>

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

Formats the value using the given formatter.

impl<T> Default for MinMaxHeap<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T> Deserialize<'de> for MinMaxHeap<T>

where T: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, T: Ord + Clone + 'a> Extend<&'a T> for MinMaxHeap<T>

fn extend<I: IntoIterator<Item = &'a 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: Ord> Extend<T> for MinMaxHeap<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: Ord> From<Vec<T>> for MinMaxHeap<T>

fn from(vec: Vec<T>) -> Self

Converts to this type from the input type.

impl<T: Ord> FromIterator<T> for MinMaxHeap<T>

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

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

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for MinMaxHeap<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Serialize for MinMaxHeap<T>

where T: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.