Struct binomial_heap::BinomialHeap

pub struct BinomialHeap<T: Ord> { /* fields omitted */ }

A priority queue based on a binomial heap.

Like BinaryHeap, BionmialHeap is an implementation of a priority queue. Unlike BinaryHeap, BionmialHeap provides an efficient append method, at the cost of greater memory usage, slower iteration, and poor cache locality.

Time Complexity

Operation	Time Complexity
append	O(log n) (amortized)
peek	O(log n)
pop	O(log n)
push	O(1) (amortized)
push_pop	O(log n)
replace	O(log n)

Methods

impl<T: Ord> BinomialHeap<T>

fn new() -> Self

Returns a new heap.

fn is_empty(&self) -> bool

Checks if the heap is empty.

fn len(&self) -> usize

Returns the number of items in the heap.

fn iter(&self) -> Iter<T>

Returns an iterator that yields references to the items in the heap in arbitrary order.

fn peek(&self) -> Option<&T>

Returns a reference to the greatest item in the heap.

Returns None if the heap is empty.

fn push(&mut self, item: T)

Pushes the given item onto the heap.

fn append(&mut self, other: &mut Self)

Moves the given heap's items into the heap, leaving the given heap empty.

This is equivalent to, but likely to be faster than, the following:

heap.extend(heap2.drain());

fn push_pop(&mut self, item: T) -> T

Pushes the given item onto the heap, then removes the greatest item in the heap and returns it.

This method is equivalent to, but likely faster than, the following:

heap.push(item);
let max = heap.pop().unwrap();

fn replace(&mut self, item: T) -> Option<T>

Removes the greatest item in the heap, then pushes the given item onto the heap.

Returns the item that was removed, or None if the heap was empty.

This method is equivalent to, but likely faster than, the following:

let max = heap.pop();
heap.push(item);

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

Removes the greatest item in the heap and returns it.

Returns None if the heap was empty.

If a call to this method is immediately preceded by a call to push, consider using push_pop instead. If a call to this method is immediately followed by a call to push, consider using replace instead.

fn clear(&mut self)

Removes all items from the heap.

fn drain(&mut self) -> Drain<T>

Removes all items from the heap and returns an iterator that yields them in arbitrary order.

All items are removed even if the iterator is not exhausted. However, the behavior of this method is unspecified if the iterator is leaked (e.g. via mem::forget).

Trait Implementations

impl<T: Clone + Ord> Clone for BinomialHeap<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Ord + Debug> Debug for BinomialHeap<T>

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

Formats the value using the given formatter.

impl<T: Ord> Default for BinomialHeap<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T: Ord> Extend<T> for BinomialHeap<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, items: I)

Extends a collection with the contents of an iterator.

impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinomialHeap<T>

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, items: I)

Extends a collection with the contents of an iterator.

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

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

Creates a value from an iterator.

impl<'a, T: 'a + Ord + Copy> FromIterator<&'a T> for BinomialHeap<T>

fn from_iter<I: IntoIterator<Item = &'a T>>(items: I) -> Self

Creates a value from an iterator.

impl<T: Ord> IntoIterator for BinomialHeap<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) -> IntoIter<T>

Creates an iterator from a value.

impl<'a, T: Ord> IntoIterator for &'a BinomialHeap<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) -> Iter<'a, T>

Creates an iterator from a value.