Struct splay_tree::SplayHeap

pub struct SplayHeap<T> { /* private fields */ }

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

Implementations

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 peek_immut(&self) -> Option<&T>

Immutable version of SplayHeap::peek().

Note that this method could be less efficient than the mutable version.

Examples

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

heap.push(1);
heap.push(5);
heap.push(2);
assert_eq!(heap.peek_immut(), 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>

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: 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, f: &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<'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.

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

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> FromIterator<T> for SplayHeap<T>where
    T: Ord,

fn from_iter<I>(iter: I) -> Selfwhere
    I: IntoIterator<Item = T>,

Creates a value from an iterator.

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