Struct pairing_heap::PairingHeap

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

A priority queue based on a pairing heap.

Like BinaryHeap, PairingHeap is an implementation of a priority queue. Unlike BinaryHeap, PairingHeap provides an append method whose runtime is asymptotically optimal, at the cost of greater memory usage, slower iteration, and poor cache locality.

Time Complexity

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

Methods

impl<T: Ord> PairingHeap<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 PairingHeap<T>

fn clone(&self) -> PairingHeap<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 PairingHeap<T>

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the "default value" for a type.

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

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

Extends a collection with the contents of an iterator.

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

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

Creates a value from an iterator.

impl<T: Ord> IntoIterator for PairingHeap<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 PairingHeap<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.