Struct 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 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 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 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 get_mut(&mut self, pos: usize) -> Option<PosMut<'_, T>>

Returns a mutable reference to the item with given position, or None if the position is out of bounds.

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

Examples

Basic usage:

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

beap.push(1);
beap.push(5);
beap.push(2);
beap.push(3);
beap.push(0);
{
    let mut val = beap.get_mut(3).unwrap();
    assert_eq!(*val, 1);
    *val = 10;
}
assert_eq!(beap.peek(), Some(&10));
assert!(beap.get_mut(100).is_none());

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 index(&self, val: &T) -> Option<usize>

Find the index of an element with given value or return None if such element does not exist.

Time complexity: O(sqrt(2n)).

Algorithm

Let there be Beap

         9
       8   7
     6   5   4
   3   2   1   0

Consider it as the upper left corner of the matrix:

   9 7 4 0
   8 5 1
   6 2
   3

Let’s start the search from the upper-right corner (the last element of the inner vector).

1. If the priority of the desired element is greater than that of the element in the current position, then move to the left along the line.

2. If the priority of the desired element is less than that of the element in the current position, then move it down the column,

3. and if there is no element at the bottom, then move down and to the left (= left on the last layer of the heap).

4. As soon as we find an element with equal val priority, we return its index, and if we find ourselves in the left in the lower corner and the value in it is not equal to val, so the desired element does not exist and it’s time to return None.

Example

use beap::Beap;

let b = Beap::<i32>::from([1, 2, 3, 4, 5, 6, 7, 8, 9]);
assert_eq!(b.index(&9), Some(0));
assert_eq!(b.index(&4), Some(5));
assert_eq!(b.index(&1), Some(8));
assert_eq!(b.index(&999), None);

pub fn remove_index(&mut self, pos: usize) -> Option<T>

Remove an element at the specified position.

If the passed index is greater than the max index of the beap, it returns None.

Time complexity

O(sqrt(2n))

Examples

use beap::Beap;

let mut b = Beap::from([1, 2, 3, 4, 5, 6, 7, 8, 9]);
assert_eq!(b.remove_index(7), Some(2));
assert_eq!(b.remove_index(0), Some(9));

let idx4 = b.index(&4).unwrap();
assert_eq!(b.remove_index(idx4), Some(4));

assert_eq!(b.remove_index(100), None);

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 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 get(&self, pos: usize) -> Option<&T>

Get an item at the specified position.

Returns None if the pos goes beyond the beap.

Time complexity

Cost is O(1) in the worst case.

Examples

use beap::Beap;

let b = Beap::from([1, 3, 2, 4]);
assert_eq!(b.get(0), Some(&4));
assert_eq!(b.get(3), Some(&1));
assert_eq!(b.get(100), None);

impl<T> Beap<T>

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

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 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 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 as_slice(&self) -> &[T]

Extracts a slice containing the underlying vector.

Example

use beap::Beap;
let b = Beap::from([1, 2]);
assert_eq!(b.as_slice(), &[2, 1]);

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

pub fn leak<'a>(self) -> &'a mut [T]

Consumes and leaks the Vec, returning a mutable reference to the contents, &'a mut [T].

This calls Vec::leak, accordingly, there are all lifetime restrictions.

Example

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

let static_ref: &'static mut [usize] = x.leak();
assert_eq!(static_ref, &[3, 2, 1]);

static_ref[0] += 1;
assert_eq!(static_ref, &[4, 2, 1]);

// Manually free it later.
unsafe {
    let _b = Box::from_raw(static_ref as *mut [usize]);
}

pub fn into_boxed_slice(self) -> Box<[T]>

Converts the beap into Box<[T]>.

It just calls Vec::into_boxed_slice on underlying Vec. Before doing the conversion, this method discards excess capacity like shrink_to_fit.

Examples

use beap::Beap;
let b = Beap::from([1, 2, 3]);
let slice = b.into_boxed_slice();

Any excess capacity is removed:

use beap::Beap;
let mut b = Vec::with_capacity(10);
b.extend([1, 2, 3]);

assert!(b.capacity() >= 10);
let slice = b.into_boxed_slice();
assert_eq!(slice.into_vec().capacity(), 3);

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>

Tries to reserve capacity for at least additional more elements to be inserted in the underlying Vec<T>. The underlying Vec may reserve more space to speculatively avoid frequent reallocations. After calling try_reserve, capacity will be greater than or equal to self.len() + additional if it returns Ok(()). Does nothing if capacity is already sufficient. This method preserves the contents even if an error occurs.

Errors

If the capacity overflows, or the allocator reports a failure, then an error is returned.

Examples

use beap::Beap;
use std::collections::TryReserveError;

fn process_data(data: &[u32]) -> Result<Beap<u32>, TryReserveError> {
    let mut output = Beap::new();

    // Pre-reserve the memory, exiting if we can't
    output.try_reserve(data.len())?;

    // Now we know this can't OOM in the middle of our complex work
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // very complicated
    }));

    Ok(output)
}
process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");

pub fn try_reserve_exact( &mut self, additional: usize, ) -> Result<(), TryReserveError>

Tries to reserve the minimum capacity for at least additional elements to be inserted in the underlying Vec<T>. Unlike try_reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations. After calling try_reserve_exact, capacity will be greater than or equal to self.len() + additional if it returns Ok(()). 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 try_reserve if future insertions are expected.

Errors

If the capacity overflows, or the allocator reports a failure, then an error is returned.

Examples

use beap::Beap;
use std::collections::TryReserveError;

fn process_data(data: &[u32]) -> Result<Beap<u32>, TryReserveError> {
    let mut output = Beap::new();

    // Pre-reserve the memory, exiting if we can't
    output.try_reserve_exact(data.len())?;

    // Now we know this can't OOM in the middle of our complex work
    output.extend(data.iter().map(|&val| {
        val * 2 + 5 // very complicated
    }));

    Ok(output)
}
process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");

Trait Implementations

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

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Default for Beap<T>

fn default() -> Self

Returns the “default value” for a type.

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>> 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<'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?

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?