Expand 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(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:
Structs
A priority queue implemented with a bi-parental heap (beap).
A draining iterator over the elements of a Beap.
An owning iterator over the elements of a Beap.
An iterator over the elements of a Beap.
Structure wrapping a mutable reference to the greatest item on a Beap.
Structure wrapping a mutable reference to the smallest item on a Beap.