Struct pairing_heap::PairingHeap
[−]
[src]
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>
[src]
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>
[src]
fn clone(&self) -> PairingHeap<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<T: Ord + Debug> Debug for PairingHeap<T>
[src]
impl<T: Ord> Default for PairingHeap<T>
[src]
impl<T: Ord> Extend<T> for PairingHeap<T>
[src]
fn extend<I: IntoIterator<Item = T>>(&mut self, items: I)
Extends a collection with the contents of an iterator. Read more
impl<T: Ord> FromIterator<T> for PairingHeap<T>
[src]
fn from_iter<I: IntoIterator<Item = T>>(items: I) -> Self
Creates a value from an iterator. Read more
impl<T: Ord> IntoIterator for PairingHeap<T>
[src]
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. Read more