Struct MedianHeap

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

A data structure for efficiently calculating a running median.

Example

use rust_dsa::{MedianHeap, Median};

// First, we create a new heap.
let mut heap = MedianHeap::new();

// Then we can add values in any order.
heap.insert(4);
heap.insert(1);
heap.insert(3);
heap.insert(6);
heap.insert(2);

// We can get the median value.
assert_eq!(heap.median(), Some(Median::One(&3)));

heap.insert(9);

// If the heap size is even, there are two medians.
assert_eq!(heap.median(), Some(Median::Two(&3, &4)));

// We can pop the median value.
assert_eq!(heap.pop(), Some(3));
assert_eq!(heap.pop(), Some(4));

// And we can add values from an iterator.
heap.extend(3..8);

assert_eq!(heap.median(), Some(Median::One(&5)));
assert_eq!(heap.len(), 9);

Runtime complexity

Operation	Runtime Complexity
MedianHeap::insert	O(log n)
MedianHeap::median	O(1)
MedianHeap::pop	O(log n)

Implementations

impl<T> MedianHeap<T>

pub fn new() -> Self

where T: Ord,

pub fn insert(&mut self, value: T)

where T: Ord,

Inserts a new value into the heap.

Example

use rust_dsa::{Median, MedianHeap};

let mut heap = MedianHeap::new();

heap.insert(5);
heap.insert(2);

assert_eq!(heap.median(), Some(Median::Two(&2, &5)));

heap.insert(3);

assert_eq!(heap.median(), Some(Median::One(&3)));

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

where T: Ord,

Pops the median element from the heap.

If there are two median values (i.e., MedianHeap::median would return Median::Two), then this function returns the smaller of the two values.

Example

use rust_dsa::MedianHeap;

let mut heap: MedianHeap<_> = "acb".chars().collect();

assert_eq!(heap.pop(), Some('b'));
assert_eq!(heap.pop(), Some('a'));
assert_eq!(heap.pop(), Some('c'));
assert_eq!(heap.pop(), None);

pub fn median(&self) -> Option<Median<'_, T>>

Returns one or two median values in the heap, or None if the heap is empty.

Example

use rust_dsa::{Median, MedianHeap};

let mut heap = MedianHeap::from([13, 8, 5, 3, 2, 1, 1]);
assert_eq!(heap.median(), Some(Median::One(&3)));

heap.pop();
assert_eq!(heap.median(), Some(Median::Two(&2, &5)));

heap.clear();
assert_eq!(heap.median(), None);

pub fn len(&self) -> usize

Returns the number of elements in the heap.

Example

use rust_dsa::MedianHeap;

let mut heap: MedianHeap<_> = "abcdefgh".chars().collect();
assert_eq!(heap.len(), 8);

heap.extend("xyz".chars());
assert_eq!(heap.len(), 11);

pub fn is_empty(&self) -> bool

Returns true if the heap is empty.

Example

use rust_dsa::MedianHeap;

let mut heap = MedianHeap::from([1, 2, 3]);
assert!(!heap.is_empty());

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

pub fn clear(&mut self)

Clears the heap.

Example

use rust_dsa::MedianHeap;

let mut heap = MedianHeap::from(["foo", "bar", "baz"]);
assert!(!heap.is_empty());

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

Trait Implementations

impl<T: Clone> Clone for MedianHeap<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Default for MedianHeap<T>

where T: Ord,

fn default() -> Self

Returns the “default value” for a type.

impl<T> Extend<T> for MedianHeap<T>

where T: Ord,

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

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, const N: usize> From<[T; N]> for MedianHeap<T>

where T: Ord,

fn from(array: [T; N]) -> Self

Converts to this type from the input type.

impl<T> FromIterator<T> for MedianHeap<T>

where T: Ord,

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

Creates a value from an iterator.