Struct splay_tree::SplayHeap

pub struct SplayHeap<T> { /* 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, 

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

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

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

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

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

Important traits for Iter<'a, T>

impl<'a, T: 'a> Iterator for Iter<'a, T> type Item = &'a T;

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

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

pub 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: Debug> Debug for SplayHeap<T>

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

Formats the value using the given formatter.

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