Bi-parental heap

• Documentation
• Crate

Description

A priority queue implemented with a bi-parental heap.

Beap (bi-parental heap) is an implict data structure which allows efficient insertion and searching of elements, requiring low (O(1)) overhead.

Insertion and popping the largest element have O(sqrt(2n)) time complexity. Checking the largest element is O(1). Converting a vector to a beap can be done by using sorting, and has O(nlog(n)) time complexity. Despite the insertion and popping operations that are slower compared to the classical binary heap, the bi-parental heap has an important advantage: searching and removing an arbitrary element, as well as finding the minimum, have the asymptotics O(sqrt(2n),) while the binary heap has O(n).

This create presents an implementation of the bi-parental heap - Beap, which has an identical interface with BinaryHeap from std::collections, and at the same time it has several new useful methods.

Read about bi-parental heap:

• Wikipedia

Usage

As a library

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

If you have any comments or suggestions, or you suddenly found an error, please start a new issue or pool request.