Struct beap::Beap

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

A priority queue implemented with a bi-parental heap (beap).

This will be a max-heap.

Examples

use beap::Beap;

// Type inference lets us omit an explicit type signature (which
// would be `Beap<i32>` in this example).
let mut beap = Beap::new();

// We can use peek to look at the next item in the beap. In this case,
// there's no items in there yet so we get None.
assert_eq!(beap.peek(), None);

// Let's add some scores...
beap.push(1);
beap.push(5);
beap.push(2);

// Now peek shows the most important item in the beap.
assert_eq!(beap.peek(), Some(&5));

// We can check the length of a beap.
assert_eq!(beap.len(), 3);

// We can iterate over the items in the beap, although they are returned in
// a random order.
for x in beap.iter() {
    println!("{}", x);
}

// If we instead pop these scores, they should come back in order.
assert_eq!(beap.pop(), Some(5));
assert_eq!(beap.pop(), Some(2));
assert_eq!(beap.pop(), Some(1));
assert_eq!(beap.pop(), None);

// We can clear the beap of any remaining items.
beap.clear();

// The beap should now be empty.
assert!(beap.is_empty())

A Beap with a known list of items can be initialized from an array:

use beap::Beap;

let beap = Beap::from([1, 5, 2]);

Min-heap

Either core::cmp::Reverse or a custom Ord implementation can be used to make Beap a min-heap. This makes beap.pop() return the smallest value instead of the greatest one.

use beap::Beap;
use std::cmp::Reverse;

let mut beap = Beap::new();

// Wrap values in `Reverse`
beap.push(Reverse(1));
beap.push(Reverse(5));
beap.push(Reverse(2));

// If we pop these scores now, they should come back in the reverse order.
assert_eq!(beap.pop(), Some(Reverse(1)));
assert_eq!(beap.pop(), Some(Reverse(2)));
assert_eq!(beap.pop(), Some(Reverse(5)));
assert_eq!(beap.pop(), None);

Sorting

use beap::Beap;

let beap = Beap::from([5, 3, 1, 7]);
assert_eq!(beap.into_sorted_vec(), vec![1, 3, 5, 7]);

Implementations

impl<T: Ord> Beap<T>

pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>>

Returns a mutable reference to the greatest item in the beap, or None if it is empty.

Note: If the PeekMut value is leaked, the beap may be in an inconsistent state.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
assert!(beap.peek_mut().is_none());

beap.push(1);
beap.push(5);
beap.push(2);
{
    let mut val = beap.peek_mut().unwrap();
    *val = 0;
}
assert_eq!(beap.peek(), Some(&2));

Time complexity

If the item is modified then the worst case time complexity is O(sqrt(2n)), otherwise it’s O(1).

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

Pushes an item onto the beap.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
beap.push(3);
beap.push(5);
beap.push(1);

assert_eq!(beap.len(), 3);
assert_eq!(beap.peek(), Some(&5));

Time complexity

O(sqrt(2n))

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

Removes the greatest item from the beap and returns it, or None if it is empty.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::from(vec![1, 3]);

assert_eq!(beap.pop(), Some(3));
assert_eq!(beap.pop(), Some(1));
assert_eq!(beap.pop(), None);

Time complexity

The worst case cost of pop on a beap containing n elements is O(sqrt(2n)).

pub fn pushpop(&mut self, item: T) -> T

Effective equivalent to a sequential push() and pop() calls.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
assert_eq!(beap.pushpop(5), 5);
assert!(beap.is_empty());

beap.push(10);
assert_eq!(beap.pushpop(20), 20);
assert_eq!(beap.peek(), Some(&10));

assert_eq!(beap.pushpop(5), 10);
assert_eq!(beap.peek(), Some(&5));

Time complexity

If the beap is empty or the element being added is larger (or equal) than the current top of the heap, then the time complexity will be O(1), otherwise O(sqrt(2n)). And unlike the sequential call of push() and pop(), the resizing never happens.

pub fn contains(&self, val: &T) -> bool

Returns true if the beap contains a value.

Examples

Basic usage:

use beap::Beap;
let beap = Beap::from([1, 5, 3, 7]);

assert!(beap.contains(&1));
assert!(beap.contains(&5));
assert!(!beap.contains(&0));

Time complexity

O(sqrt(2n))

pub fn remove(&mut self, val: &T) -> bool

Removes a value from the beap. Returns whether the value was present in the beap.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::from([1, 5, 3]);

assert!(beap.remove(&3));
assert!(!beap.remove(&3));
assert_eq!(beap.len(), 2);

Time complexity

O(sqrt(2n))

pub fn replace(&mut self, old: &T, new: T) -> bool

Replaces the first found element with the value old with the value new, returns true if the element old was found.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
beap.push(5);
beap.push(10);

assert!(beap.replace(&10, 100));
assert!(!beap.replace(&1, 200));

assert_eq!(beap.into_sorted_vec(), vec![5, 100]);

Time complexity

O(sqrt(2n)).

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

Returns the smallest item in the beap, or None if it is empty.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
assert_eq!(beap.tail(), None);

beap.push(9);
beap.push(3);
beap.push(6);
assert_eq!(beap.tail(), Some(&3));

Time complexity

O(sqrt(2n))

pub fn tail_mut(&mut self) -> Option<TailMut<'_, T>>

Returns a mutable reference to the smallest item in the beap, or None if it is empty.

Note: If the TailMut value is leaked, the beap may be in an inconsistent state.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
assert!(beap.tail_mut().is_none());

beap.push(1);
beap.push(5);
beap.push(2);
{
    let mut val = beap.tail_mut().unwrap();
    *val = 10;
}
assert_eq!(beap.tail(), Some(&2));

Time complexity

O(sqrt(2n)),

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

Removes the smallest item from the beap and returns it, or None if it is empty.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::from(vec![1, 3]);

assert_eq!(beap.pop_tail(), Some(1));
assert_eq!(beap.pop_tail(), Some(3));
assert_eq!(beap.pop_tail(), None);

Time complexity

O(sqrt(2n)).

pub fn into_sorted_vec(self) -> Vec<T>

Consumes the Beap and returns a vector in sorted (ascending) order.

Examples

Basic usage:

use beap::Beap;

let mut beap = Beap::from(vec![1, 2, 4, 5, 7]);
beap.push(6);
beap.push(3);

let vec = beap.into_sorted_vec();
assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7]);

Time complexity

O(nlog(n))

Inside, Vec::sort_unstable is used.

pub fn append(&mut self, other: &mut Self)

Moves all the elements of other into self, leaving other empty.

Examples

Basic usage:

use beap::Beap;

let v = vec![-10, 1, 2, 3, 3];
let mut a = Beap::from(v);

let v = vec![-20, 5, 43];
let mut b = Beap::from(v);

a.append(&mut b);

assert_eq!(a.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
assert!(b.is_empty());

Time complexity

Operation can be done in O(n*log(n)), where n = self.len() + other.len().

pub fn append_vec(&mut self, other: &mut Vec<T>)

Moves all the elements of other into self, leaving other empty.

Examples

Basic usage:

use beap::Beap;

let mut beap = Beap::from([-10, 1, 2, 3, 3]);

let mut v = vec![-20, 5, 43];
beap.append_vec(&mut v);

assert_eq!(beap.into_sorted_vec(), [-20, -10, 1, 2, 3, 3, 5, 43]);
assert!(v.is_empty());

Time complexity

Operation can be done in O(n*log(n)), where n = self.len() + other.len().

impl<T> Beap<T>

pub fn new() -> Beap<T>

Creates an empty Beap as a max-beap.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
assert!(beap.is_empty());

beap.push(4);
assert_eq!(beap.len(), 1);

pub fn iter(&self) -> Iter<'_, T>

Returns an iterator visiting all values in the underlying vector, in arbitrary order.

Examples

Basic usage:

use beap::Beap;
let beap = Beap::from(vec![1, 2, 3, 4]);

// Print 1, 2, 3, 4 in arbitrary order
for x in beap.iter() {
    println!("{}", x);
}

assert_eq!(beap.into_sorted_vec(), vec![1, 2, 3, 4]);

pub fn with_capacity(capacity: usize) -> Beap<T>

Creates an empty Beap with a specific capacity. This preallocates enough memory for capacity elements, so that the Beap does not have to be reallocated until it contains at least that many values.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::with_capacity(10);
beap.push(4);

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

Returns the greatest item in the beap, or None if it is empty.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
assert_eq!(beap.peek(), None);

beap.push(1);
beap.push(5);
beap.push(2);
assert_eq!(beap.peek(), Some(&5));

Time complexity

Cost is O(1) in the worst case.

pub fn capacity(&self) -> usize

Returns the number of elements the beap can hold without reallocating.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::with_capacity(100);
assert!(beap.capacity() >= 100);
beap.push(4);

pub fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for exactly additional more elements to be inserted in the given Beap. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

Panics

Panics if the new capacity overflows usize.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
beap.reserve_exact(100);
assert!(beap.capacity() >= 100);
beap.push(4);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the Beap. The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the new capacity overflows usize.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();
beap.reserve(100);
assert!(beap.capacity() >= 100);
beap.push(4);

pub fn shrink_to_fit(&mut self)

Discards as much additional capacity as possible.

Examples

Basic usage:

use beap::Beap;
let mut beap: Beap<i32> = Beap::with_capacity(100);

assert!(beap.capacity() >= 100);
beap.shrink_to_fit();
assert!(beap.capacity() == 0);

pub fn shrink_to(&mut self, min_capacity: usize)

Discards capacity with a lower bound.

The capacity will remain at least as large as both the length and the supplied value.

If the current capacity is less than the lower limit, this is a no-op.

Examples

use beap::Beap;
let mut beap: Beap<i32> = Beap::with_capacity(100);

assert!(beap.capacity() >= 100);
beap.shrink_to(10);
assert!(beap.capacity() >= 10);

pub fn into_vec(self) -> Vec<T>

Consumes the Beap<T> and returns the underlying vector Vec in arbitrary order.

Examples

Basic usage:

use beap::Beap;
let beap = Beap::from(vec![1, 2, 3, 4, 5, 6, 7]);
let vec = beap.into_vec();

// Will print in some order
for x in vec {
    println!("{}", x);
}

pub fn len(&self) -> usize

Returns the length of the beap.

Examples

Basic usage:

use beap::Beap;
let beap = Beap::from(vec![1, 3]);

assert_eq!(beap.len(), 2);

pub fn is_empty(&self) -> bool

Checks if the beap is empty.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::new();

assert!(beap.is_empty());

beap.push(3);
beap.push(5);
beap.push(1);

assert!(!beap.is_empty());

pub fn drain(&mut self) -> Drain<'_, T>

Clears the bi-parental heap, returning an iterator over the removed elements in arbitrary order. If the iterator is dropped before being fully consumed, it drops the remaining elements in arbitrary order.

The returned iterator keeps a mutable borrow on the beap to optimize its implementation.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::from([1, 3, 5]);

assert!(!beap.is_empty());

for x in beap.drain() {
    println!("{}", x);
}

assert!(beap.is_empty());

pub fn clear(&mut self)

Drops all items from the beap.

Examples

Basic usage:

use beap::Beap;
let mut beap = Beap::from([1, 3, 5]);

assert!(!beap.is_empty());

beap.clear();

assert!(beap.is_empty());

Trait Implementations

impl<T: Clone> Clone for Beap<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for Beap<T>

fn extend<I: IntoIterator<Item = &'a 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: Ord> Extend<T> for Beap<T>

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

Extend Beap with elements from the iterator.

Examples

Basic usage:

use beap::Beap;

let mut beap = Beap::new();
beap.extend(vec![7, 1, 0, 4, 5, 3]);
assert_eq!(beap.into_sorted_vec(), [0, 1, 3, 4, 5, 7]);

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

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

Converts a [T, N] into a Beap<T>.

This conversion has O(nlog(n)) time complexity.

Examples

Basic usage:

use beap::Beap;

let mut b1 = Beap::from([1, 4, 2, 3]);
let mut b2: Beap<_> = [1, 4, 2, 3].into();
assert_eq!(b1.into_vec(), vec![4, 3, 2, 1]);
assert_eq!(b2.into_vec(), vec![4, 3, 2, 1]);

impl<T: Ord> From<Vec<T, Global>> for Beap<T>

fn from(vec: Vec<T>) -> Beap<T>

Converts a Vec<T> into a Beap<T>.

This conversion happens in-place, and has O(n) time complexity.

Examples

Basic usage:

use beap::Beap;
let beap = Beap::from(vec![5, 3, 2, 4, 1]);
assert_eq!(beap.into_sorted_vec(), vec![1, 2, 3, 4, 5]);

impl<T: Ord> FromIterator<T> for Beap<T>

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

Building Beap from iterator.

This conversion has O(nlog(n)) time complexity.

Examples

Basic usage:

use beap::Beap;

let mut b1 = Beap::from([1, 4, 2, 3]);
let mut b2: Beap<i32> = [1, 4, 2, 3].into_iter().collect();
while let Some((a, b)) = b1.pop().zip(b2.pop()) {
    assert_eq!(a, b);
}

impl<T> IntoIterator for Beap<T>

fn into_iter(self) -> IntoIter<T>

Creates a consuming iterator, that is, one that moves each value out of the beap in arbitrary order. The beap cannot be used after calling this.

Examples

Basic usage:

use beap::Beap;
let beap = Beap::from(vec![1, 2, 3, 4]);

// Print 1, 2, 3, 4 in arbitrary order
for x in beap.into_iter() {
    // x has type i32, not &i32
    println!("{}", x);
}

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

impl<'a, T> IntoIterator for &'a Beap<T>

fn into_iter(self) -> Iter<'a, T>

Returns an iterator visiting all values in the underlying vector, in arbitrary order.

Examples

Basic usage:

use beap::Beap;
let beap = Beap::from(vec![1, 2, 3, 4]);

// Print 1, 2, 3, 4 in arbitrary order
for x in &beap {
    // x has type &i32
    println!("{}", x);
}

assert_eq!(beap.into_sorted_vec(), vec![1, 2, 3, 4]);

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?