Struct min_max_heap::MinMaxHeap
source · pub struct MinMaxHeap<T>(_);
Expand description
A double-ended priority queue.
Most operations are O(log n).
Implementations
sourceimpl<T> MinMaxHeap<T>
impl<T> MinMaxHeap<T>
sourcepub fn with_capacity(len: usize) -> Self
pub fn with_capacity(len: usize) -> Self
Creates a new, empty MinMaxHeap
with space allocated to hold
len
elements.
O(n).
sourceimpl<T: Ord> MinMaxHeap<T>
impl<T: Ord> MinMaxHeap<T>
sourcepub fn push(&mut self, element: 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.
sourcepub fn push_pop_min(&mut self, element: T) -> T
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).
sourcepub fn push_pop_max(&mut self, element: T) -> T
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).
sourcepub fn replace_min(&mut self, element: T) -> Option<T>
pub fn replace_min(&mut self, element: T) -> Option<T>
Pops the minimum, then pushes an element in an optimized fashion.
O(log n).
sourcepub fn replace_max(&mut self, element: T) -> Option<T>
pub fn replace_max(&mut self, element: T) -> Option<T>
Pops the maximum, then pushes an element in an optimized fashion.
O(log n).
sourcepub fn into_vec_asc(self) -> Vec<T>
pub fn into_vec_asc(self) -> Vec<T>
Returns an ascending (sorted) vector, reusing the heap’s storage.
O(n log n).
sourcepub fn into_vec_desc(self) -> Vec<T>
pub fn into_vec_desc(self) -> Vec<T>
Returns an descending (sorted) vector, reusing the heap’s storage.
O(n log n).
sourceimpl<T> MinMaxHeap<T>
impl<T> MinMaxHeap<T>
sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
The number of elements the heap can hold without reallocating.
O(1)
sourcepub fn reserve_exact(&mut self, additional: usize)
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
.
sourcepub fn reserve(&mut self, additional: 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
.
sourcepub fn shrink_to_fit(&mut self)
pub fn shrink_to_fit(&mut self)
Discards extra capacity.
O(n)
sourcepub fn into_vec(self) -> Vec<T>
pub fn into_vec(self) -> Vec<T>
Consumes the MinMaxHeap
and returns its elements in a vector
in arbitrary order.
O(n)
sourcepub fn iter(&self) -> Iter<'_, T>ⓘNotable traits for Iter<'a, T>impl<'a, T> Iterator for Iter<'a, T> type Item = &'a T;
pub fn iter(&self) -> Iter<'_, T>ⓘNotable traits for Iter<'a, T>impl<'a, T> Iterator for Iter<'a, T> type Item = &'a 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.
sourcepub fn drain(&mut self) -> Drain<'_, T>ⓘNotable traits for Drain<'a, T>impl<'a, T> Iterator for Drain<'a, T> type Item = T;
pub fn drain(&mut self) -> Drain<'_, T>ⓘNotable traits for Drain<'a, T>impl<'a, T> Iterator for Drain<'a, T> type Item = 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.
sourcepub fn drain_asc(&mut self) -> DrainAsc<'_, T>ⓘNotable traits for DrainAsc<'a, T>impl<'a, T: Ord> Iterator for DrainAsc<'a, T> type Item = T;
pub fn drain_asc(&mut self) -> DrainAsc<'_, T>ⓘNotable traits for DrainAsc<'a, T>impl<'a, T: Ord> Iterator for DrainAsc<'a, T> type Item = 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.
sourcepub fn drain_desc(&mut self) -> DrainDesc<'_, T>ⓘNotable traits for DrainDesc<'a, T>impl<'a, T: Ord> Iterator for DrainDesc<'a, T> type Item = T;
pub fn drain_desc(&mut self) -> DrainDesc<'_, T>ⓘNotable traits for DrainDesc<'a, T>impl<'a, T: Ord> Iterator for DrainDesc<'a, T> type Item = 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
sourceimpl<T: Clone> Clone for MinMaxHeap<T>
impl<T: Clone> Clone for MinMaxHeap<T>
sourcefn clone(&self) -> MinMaxHeap<T>
fn clone(&self) -> MinMaxHeap<T>
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresourceimpl<T: Debug> Debug for MinMaxHeap<T>
impl<T: Debug> Debug for MinMaxHeap<T>
sourceimpl<T> Default for MinMaxHeap<T>
impl<T> Default for MinMaxHeap<T>
sourceimpl<'de, T> Deserialize<'de> for MinMaxHeap<T>where
T: Deserialize<'de>,
impl<'de, T> Deserialize<'de> for MinMaxHeap<T>where
T: Deserialize<'de>,
sourcefn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
sourceimpl<'a, T: Ord + Clone + 'a> Extend<&'a T> for MinMaxHeap<T>
impl<'a, T: Ord + Clone + 'a> Extend<&'a T> for MinMaxHeap<T>
sourcefn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)sourceimpl<T: Ord> Extend<T> for MinMaxHeap<T>
impl<T: Ord> Extend<T> for MinMaxHeap<T>
sourcefn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)