Struct skew_heap::SkewHeap

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

A skew heap.

Methods

impl<T: Ord> SkewHeap<T>

fn new() -> Self

Returns an empty heap.

fn is_empty(&self) -> bool

Returns true if the heap contains no items.

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 heap's items in arbitrary order.

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

Returns a reference to the heap's greatest item.

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 all items from the given heap into the heap.

Examples

use skew_heap::SkewHeap;

let mut h1 = SkewHeap::new();
h1.push(4);
h1.push(2);
h1.push(3);

let mut h2 = SkewHeap::new();
h2.push(1);
h2.push(8);

h1.append(&mut h2);

assert_eq!(h1.len(), 5);
assert_eq!(h1.peek(), Some(&8));

assert_eq!(h2.len(), 0);
assert_eq!(h2.peek(), None);

fn clear(&mut self)

Removes all items from the heap.

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

Removes the heap's greatest item and returns it.

Returns None if the heap was empty.

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

Pushes the given item onto to the heap, then removes the heap's greatest item and returns it.

Examples

use skew_heap::SkewHeap;

let mut h = SkewHeap::new();

assert_eq!(h.push_pop(5), 5);
assert_eq!(h.len(), 0);
assert_eq!(h.peek(), None);

h.extend(&[4, 5]);
assert_eq!(h.len(), 2);
assert_eq!(h.peek(), Some(&5));

assert_eq!(h.push_pop(6), 6);
assert_eq!(h.len(), 2);
assert_eq!(h.peek(), Some(&5));

assert_eq!(h.push_pop(3), 5);
assert_eq!(h.len(), 2);
assert_eq!(h.peek(), Some(&4));

assert_eq!(h.pop(), Some(4));
assert_eq!(h.pop(), Some(3));
assert_eq!(h.pop(), None);

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

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

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

Examples

use skew_heap::SkewHeap;

let mut h = SkewHeap::new();

assert_eq!(h.replace(5), None);
assert_eq!(h.len(), 1);
assert_eq!(h.peek(), Some(&5));

assert_eq!(h.replace(4), Some(5));
assert_eq!(h.len(), 1);
assert_eq!(h.peek(), Some(&4));

assert_eq!(h.replace(6), Some(4));
assert_eq!(h.len(), 1);
assert_eq!(h.peek(), Some(&6));

assert_eq!(h.pop(), Some(6));
assert_eq!(h.pop(), None);

Trait Implementations

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

fn default() -> Self

Returns the "default value" for a type.

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

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Ord> Extend<T> for SkewHeap<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 SkewHeap<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 SkewHeap<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 SkewHeap<T>

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

Creates a value from an iterator.

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

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

Formats the value using the given formatter.

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