Struct PairingHeap

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

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)

Implementations

impl<T: Ord> PairingHeap<T>

pub fn new() -> Self

Returns a new heap.

pub fn is_empty(&self) -> bool

Checks if the heap is empty.

pub fn len(&self) -> usize

Returns the number of items in the heap.

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

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

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

Returns a reference to the greatest item in the heap.

Returns None if the heap is empty.

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

Pushes the given item onto the heap.

pub 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());

pub 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();

pub 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);

pub 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.

pub fn clear(&mut self)

Removes all items from the heap.

pub 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 duplicate 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.

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> FromIterator<T> for PairingHeap<T>

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

Creates a value from an iterator.

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.

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.