Struct trait_based_collection::priority_queue::BinaryHeap

pub struct BinaryHeap<T>where
    T: Ord,{
    pub mode: ExpansionMode,
    /* private fields */
}

An implementation of a priority queue using a binary heap. The binary heap is implemented using an array. The binary heap is a complete binary tree, meaning that every level of the tree is filled except for the last level, which is filled from left to right. The binary heap is stored using a function that determines the order of the elements in the heap.

The default heap function is equivalent to a min-heap, meaning that the element with the smallest value is at the top of the heap. For a max-heap, the heap can be created using the max_heap function.

Examples

use trait_based_collection::{prelude::*, BinaryHeap};

let mut heap = BinaryHeap::min_heap(16, ExpansionMode::Expand(2.0));
heap.add(5);
heap.add(3);
heap.add(7);
heap.add(1);

assert_eq!(heap.remove(), Some(1));
assert_eq!(heap.remove(), Some(3));
assert_eq!(heap.remove(), Some(5));
assert_eq!(heap.remove(), Some(7));
assert_eq!(heap.remove(), None);

Fields

mode: ExpansionMode

The current mode of expansion of the deque that determinate the behaviour the collection is full. See ExpansionMode for more information.

Implementations

impl<T> BinaryHeap<T>where
    T: Ord,

pub fn new(
    capacity: usize,
    mode: ExpansionMode,
    function: fn(_: &T, _: &T) -> Ordering
) -> Self

Creates a new BinaryHeap with the given capacity, expansion mode and function that determines the order of the elements in the heap. The root of the heap is the element that has Ordering::Less when compared to the other elements in the heap.

This a generic constructor, if you want a max_heap or a min_heap, use the corresponding functions.

Panics

This function panics if the capacity is 0.

Examples

use trait_based_collection::{prelude::*, BinaryHeap};

let mut heap: BinaryHeap<i32> = BinaryHeap::new(10,
                                                ExpansionMode::Ignore,
                                                |a, b| a.cmp(b));  // Min-heap.

pub fn min_heap(capacity: usize, mode: ExpansionMode) -> Self

Creates a MinHeap with the given capacity and expansion mode.

Panics

This function panics if the capacity is 0.

Examples

use trait_based_collection::{prelude::*, BinaryHeap};

let mut heap: BinaryHeap<i32> = BinaryHeap::min_heap(10, ExpansionMode::Overwrite);

pub fn max_heap(capacity: usize, mode: ExpansionMode) -> Self

Creates a MaxHeap with the given capacity and expansion mode.

Panics

This function panics if the capacity is 0.

Examples

use trait_based_collection::{prelude::*, BinaryHeap};

let mut heap: BinaryHeap<i32> = BinaryHeap::max_heap(10, ExpansionMode::Overwrite);

Trait Implementations

impl<'a, T> Collection<'a, T> for BinaryHeap<T>where
    T: 'a + Ord,

fn new_default() -> Self

Creates a new Collection with a default capacity.

fn with_capacity(capacity: usize) -> Self

Creates a new Collection with a specific capacity.

fn with_approximate_capacity(approx_capacity: usize) -> Self

Creates a new Collection with a capacity that is at least the specified capacity.

fn add(&mut self, value: T)

Adds an item to the Collection.

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

Removes an item from the Collection.

fn clear(&mut self)

Clears all items from the Collection while keeping the capacity.

fn peek(&'a self) -> Option<Self::ItemRef>

Returns an immutable reference of the item that will be removed next.

fn peek_mut(&'a mut self) -> Option<Self::ItemMut>

Returns a mutable reference of the item that will be removed next.

fn len(&self) -> usize

Returns the number of items in the Collection.

fn get(&'a self, index: usize) -> Option<Self::ItemRef>

Returns a immutable reference to the n-th item in the Collection.

fn get_mut(&'a mut self, index: usize) -> Option<Self::ItemMut>

Returns a mutable reference to the n-th item in the Collection.

fn find(&'a self, value: &T) -> Option<usize>where
    T: PartialEq,

Searches for an item in the Collection and returns its index if found. Returns None if the item is not found.

fn contains(&'a self, value: &T) -> boolwhere
    T: PartialEq,

Checks if an item is in the Collection.

fn is_empty(&self) -> bool

Checks if the Collection is empty.

impl<T> Debug for BinaryHeap<T>where
    T: Ord + Debug,

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

Formats the value using the given formatter.

impl<T> Default for BinaryHeap<T>where
    T: Ord,

fn default() -> Self

Returns the “default value” for a type.

impl<T> Display for BinaryHeap<T>where
    T: Ord,
    T: Display,

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

Formats the value using the given formatter.

impl<T> Drop for BinaryHeap<T>where
    T: Ord,

fn drop(&mut self)

Executes the destructor for this type.

impl<T> Extend<T> for BinaryHeap<T>where
    T: Ord,

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<'a, T> FixedSizeCollection<'a, T> for BinaryHeap<T>where
    T: 'a + Ord,

fn with_mode(capacity: usize, mode: ExpansionMode) -> Self

Creates a new fixed size Collection with the specified capacity and ExpansionMode.

fn capacity(&self) -> usize

Returns the maximum amount of items that the collection can hold without expanding.

fn expand(&mut self, extra_size: usize)

Expands the capacity of the collection by at least the specified amount. This amount or more will be dded to the capacity.

fn mode(&self) -> &ExpansionMode

Returns the ExpansionMode of the collection . This is used to determine how the collection will behave when it is full.

fn is_full(&self) -> bool

Checks if the number of items in the FixedSizeCollection is equal to the capacity.

impl<T> FromIterator<T> for BinaryHeap<T>where
    T: Ord,

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

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a BinaryHeap<T>where
    T: 'a + Ord,

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = IntoIter<&'a T, Global>

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 &'a mut BinaryHeap<T>where
    T: 'a + Ord,

type Item = PeekMut<'a, T>

The type of the elements being iterated over.

type IntoIter = BinaryHeapIterMut<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for BinaryHeap<T>where
    T: Ord,

type Item = T

The type of the elements being iterated over.

type IntoIter = BinaryHeapIntoIter<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> Iterators<'a, T> for BinaryHeap<T>where
    T: 'a + Ord,

type ItemRef = &'a T

The type of reference the immutable iterator (Iter) iterates over the items in the Collection. The reference is only valid for the duration of the iteration.

type ItemMut = PeekMut<'a, T>

The type of mutable reference the mutable iterator (IterMut) iterates over the items in the Collection. The reference is only valid for the duration of the iteration.

type Iter = IntoIter<&'a T, Global>

Which kind of iterator is returned by iter.

type IterMut = BinaryHeapIterMut<'a, T>

Which kind of iterator is returned by iter_mut.

fn iter(&'a self) -> Self::Iter

Creates an immutable iterator over the items in the Collection without consuming them.

fn iter_mut(&'a mut self) -> Self::IterMut

Creates a mutable iterator over the items in the Collection without consuming them.