Struct splay_tree::SplayHeap

pub struct SplayHeap<T> {
    // some fields omitted
}

A priority queue implemented with a splay tree.

This will be a max-heap.

A splay tree based heap is a self-adjusting data structure. It performs pushing and popping in O(log n) amortized time.

It is a logic error for a key to be modified in such a way that the key's ordering relative to any other key, as determined by the Ord trait, changes while it is in the map. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

Examples

use splay_tree::SplayHeap;

let mut heap = SplayHeap::new();

heap.push(0);
heap.push(10);
heap.push(7);

assert_eq!(heap.peek(), Some(&10));
assert_eq!(heap.pop(), Some(10));
assert_eq!(heap.pop(), Some(7));
assert_eq!(heap.pop(), Some(0));
assert_eq!(heap.pop(), None);

Methods

impl<T> SplayHeap<T> where T: Ord

fn new() -> Self

Creates an empty SplayHeap as a max-heap.

Examples

use splay_tree::SplayHeap;
let mut heap = SplayHeap::new();

heap.push(10);
assert_eq!(heap.pop(), Some(10));

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

Returns the greatest item in the heap, or None if it is empty.

NOTICE

Because SplayHeap is a self-adjusting amortized data structure, this function requires the mut qualifier.

Examples

use splay_tree::SplayHeap;
let mut heap = SplayHeap::new();
assert_eq!(heap.peek(), None);

heap.push(1);
heap.push(5);
heap.push(2);
assert_eq!(heap.peek(), Some(&5));

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

Removes the greatest item from the heap and returns it, or None if it is empty.

Examples

use splay_tree::SplayHeap;
let mut heap: SplayHeap<_> = vec![1, 3].into_iter().collect();

assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);

fn push(&mut self, item: T)

Pushes an item onto the heap.

Examples

use splay_tree::SplayHeap;
let mut heap = SplayHeap::new();
heap.push(3);
heap.push(5);
heap.push(1);

assert_eq!(heap.len(), 3);
assert_eq!(heap.peek(), Some(&5));

fn clear(&mut self)

Drops all items from the heap.

Examples

use splay_tree::SplayHeap;
let mut heap: SplayHeap<_> = vec![1, 3].into_iter().collect();

assert!(!heap.is_empty());
heap.clear();
assert!(heap.is_empty());

impl<T> SplayHeap<T>

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

Returns an iterator visiting all items in sorted (descending) order.

Examples

use splay_tree::SplayHeap;
let heap: SplayHeap<_> = vec![1, 4, 2, 3].into_iter().collect();

// Print all values in `heap` in sorted order
for x in heap.iter() {
  println!("{}", x);
}

fn len(&self) -> usize

Returns the length of the heap.

Examples

use splay_tree::SplayHeap;
let heap: SplayHeap<_> = vec![1, 3].into_iter().collect();

assert_eq!(heap.len(), 2);

fn is_empty(&self) -> bool

Checkes if the heap is empty.

Examples

use splay_tree::SplayHeap;
let mut heap = SplayHeap::new();

assert!(heap.is_empty());

heap.push(1);
assert!(!heap.is_empty());

heap.pop();
assert!(heap.is_empty());

Trait Implementations

impl<T: Clone> Clone for SplayHeap<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for SplayHeap<T>

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

Formats the value using the given formatter.

impl<T> Default for SplayHeap<T> where T: Ord

fn default() -> Self

Returns the "default value" for a type.

impl<T> FromIterator<T> for SplayHeap<T> where T: Ord

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

Creates a value from an iterator.

impl<T> IntoIterator for SplayHeap<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) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a SplayHeap<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) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Extend<T> for SplayHeap<T> where T: Ord

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

Extends a collection with the contents of an iterator.

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

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

Extends a collection with the contents of an iterator.