Crate beap

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(n * log(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

Re-exports

pub use iter::Drain;

pub use iter::IntoIter;

pub use iter::Iter;

Modules

iter

Beap iterators.

Structs

Beap

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

PeekMut

Structure wrapping a mutable reference to the greatest item on a Beap.

PosMut

Structure wrapping a mutable reference to the item with provided index on a Beap.

TailMut

Structure wrapping a mutable reference to the smallest item on a Beap.