Struct IntervalHeap

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

An interval heap implementation for use as a double-ended priority queue.

Example

use rust_dsa::IntervalHeap;

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

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

// We can peek at the min and max values.
assert_eq!(heap.peek_min(), Some(&1));
assert_eq!(heap.peek_max(), Some(&6));

// And pop them off from both ends.
assert_eq!(heap.pop_min(), Some(1));
assert_eq!(heap.pop_min(), Some(3));
assert_eq!(heap.pop_max(), Some(6));
assert_eq!(heap.pop_min(), Some(4));
assert_eq!(heap.pop_min(), None);

// We can also create heaps from arrays.
let mut heap = IntervalHeap::from([2, 6, 2]);

// And heaps can contain duplicate items.
assert_eq!(heap.pop_min(), Some(2));
assert_eq!(heap.pop_min(), Some(2));

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

Runtime complexity

Operation	Runtime Complexity
IntervalHeap::insert	O(log n)
IntervalHeap::pop_min	O(log n)
IntervalHeap::pop_max	O(log n)
IntervalHeap::peek_min	O(1)
IntervalHeap::peek_max	O(1)
IntervalHeap::from	O(n log n)

Implementations

impl<T> IntervalHeap<T>

pub fn new() -> IntervalHeap<T>

Creates an empty heap.

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

where T: Ord,

Inserts a value into the heap.

Example

use rust_dsa::IntervalHeap;

let mut heap = IntervalHeap::new();

heap.insert('h');
heap.insert('n');

assert_eq!(heap.peek_min(), Some(&'h'));
assert_eq!(heap.peek_max(), Some(&'n'));

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

where T: Ord,

Removes and returns the smallest value in the heap, or None if the heap is empty.

Example

use rust_dsa::IntervalHeap;

let mut heap = IntervalHeap::from([4, 3, 6]);

assert_eq!(heap.pop_min(), Some(3));
assert_eq!(heap.pop_min(), Some(4));
assert_eq!(heap.pop_min(), Some(6));
assert_eq!(heap.pop_min(), None);

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

where T: Ord,

Removes and returns the largest value in the heap, or None if the heap is empty.

Example

use rust_dsa::IntervalHeap;

let mut heap = IntervalHeap::from([4, 3, 6]);

assert_eq!(heap.pop_max(), Some(6));
assert_eq!(heap.pop_max(), Some(4));
assert_eq!(heap.pop_max(), Some(3));
assert_eq!(heap.pop_max(), None);

pub fn peek_min(&self) -> Option<&T>

Returns a reference to the smallest value in the heap, or None if the heap is empty.

Example

use rust_dsa::IntervalHeap;

let mut heap = IntervalHeap::from(['a', 'b', 'c']);

assert_eq!(heap.peek_min(), Some(&'a'));

heap.clear();

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

pub fn peek_max(&self) -> Option<&T>

Returns a reference to the largest value in the heap, or None if the heap is empty.

Example

use rust_dsa::IntervalHeap;

let mut heap = IntervalHeap::from(['a', 'b', 'c']);

assert_eq!(heap.peek_max(), Some(&'c'));

heap.clear();

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

pub fn len(&self) -> usize

Returns the number of elements in the heap.

Example

use rust_dsa::IntervalHeap;

let mut heap: IntervalHeap<_> = (0..42).collect();

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

heap.pop_max();

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

heap.clear();

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

pub fn is_empty(&self) -> bool

Returns true if the heap is empty.

Example

use rust_dsa::IntervalHeap;

let mut heap: IntervalHeap<_> = ('a'..='z').collect();

assert!(!heap.is_empty());

heap.clear();

assert!(heap.is_empty());

pub fn clear(&mut self)

Clears the heap.

Example

use rust_dsa::IntervalHeap;

let mut heap: IntervalHeap<_> = ('a'..='z').collect();

assert!(!heap.is_empty());

heap.clear();

assert!(heap.is_empty());

Trait Implementations

impl<T: Clone> Clone for IntervalHeap<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Default for IntervalHeap<T>

fn default() -> IntervalHeap<T>

Returns the “default value” for a type.

impl<T, const N: usize> From<[T; N]> for IntervalHeap<T>

where T: Ord,

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

use rust_dsa::IntervalHeap;

let random: Vec<i32> = (0..10_000).map(|_| rand::random()).collect();

let mut sorted = random.clone();
sorted.sort();
let mut iter = sorted.into_iter();

let mut heap: IntervalHeap<_> = random.into_iter().collect();

for _ in 0..10_001 {
    if rand::random() {
        assert_eq!(heap.pop_min(), iter.next());
    } else {
        assert_eq!(heap.pop_max(), iter.next_back());
    }
}

impl<T> FromIterator<T> for IntervalHeap<T>

where T: Ord,

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

Creates a value from an iterator.