Struct medianheap::MedianHeap

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

A median heap implemented with two binary heaps.

Implementations

impl<T: Ord> MedianHeap<T>

pub fn new() -> Self

Creates an empty MedianHeap.

Examples

Basic usage:

let mut heap = MedianHeap::new();
heap.push(4);

pub fn with_max_size(max_size: usize) -> Self

Creates an empty MedianHeap which can only grow to max_size.

Panics

Panics if max_size is zero.

Examples

Basic usage:

let mut heap = MedianHeap::with_max_size(42);
heap.push(4);

pub fn max_size(&self) -> Option<usize>

Returns the maximum size the median heap can grow to.

Examples

Basic usage:

let heap = MedianHeap::<i32>::with_max_size(42);
assert_eq!(heap.max_size(), Some(42));

pub fn len(&self) -> usize

Returns the length of the heap.

Examples

Basic usage:

let mut heap = MedianHeap::new();
assert_eq!(heap.len(), 0);

heap.push(1);
assert_eq!(heap.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if there are no elements on the heap.

Examples

Basic usage:

let mut heap = MedianHeap::<i32>::new();

assert_eq!(heap.is_empty(), true);

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

This either returns

• Some(Median::Single(T)) containing the single median value if there are an odd number of elements,
• Some(Median::Pair(T, T)) containing the two middlemost values if there are an even number of elements, or
• None if the heap is empty.

Examples

Basic usage:

let mut heap = MedianHeap::new();

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

heap.push(1);
assert_eq!(heap.median(), Some(Median::Single(&1)));

heap.push(3);
assert_eq!(heap.median(), Some(Median::Pair(&1, &3)));

pub fn push(&mut self, item: T)

Pushes an item onto the median heap.

When max_size is set and the heap is full, this will remove

• the smallest item if the pushed item is greater than (>) the current median,
• the largest item, if the pushed item is less than (<) the current median, or
• both the smallest and the largest item, if the pushed item is equal (==) to the current median.

Examples

Basic usage:

let mut heap = MedianHeap::new();

heap.push(1);
heap.push(2);
heap.push(3);

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

Usage with max_size:

let mut heap = MedianHeap::with_max_size(2);

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

When we now push another 1 it will be inserted in the middle, which leads to both the smallest and largest item being removed in order not to overflow the max_size.

heap.push(1);
assert_eq!(heap.len(), 1);

impl<T: Ord + Clone> MedianHeap<T>

pub fn median_with(&self, f: impl FnOnce(&T, &T) -> T) -> Option<T>

This either returns

• Some(T) containing the median value if there are an odd number of elements,
• Some(T) containing the arithmetic mean of the two middlemost values if there are an even number of elements, or
• None if the heap is empty.

Examples

Basic usage:

let mut heap = MedianHeap::new();

heap.push(1);
heap.push(3);
assert_eq!(heap.median_with(|l, r| (l + r) / 2), Some(2));

Trait Implementations

impl<T: Clone + Ord> 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: Ord + Debug> Debug for MedianHeap<T>

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

Formats the value using the given formatter.

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

fn default() -> Self

Creates an empty MedianHeap.