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 priority, have the asymptotics O(sqrt(2n),) while 8000 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.
| Operation | Method | Time complexity |
|---|---|---|
| get max | Beap::peak |
O(1) |
| push | Beap::push |
O(sqrt(2n)) |
| pop | Beap::pop |
O(sqrt(2n)) |
| search | Beap::index |
O(sqrt(2n)) |
| remove by value | Beap::remove |
O(sqrt(2n)) |
| replace value | Beap::replace |
O(sqrt(2n)) |
| get min | Beap::tail |
O(sqrt(2n)) |
| pop min | Beap::pop_tail |
O(sqrt(2n)) |
| heapify | Beap::from |
O(n*log(n)) |
| merge | Beap::append |
O(n*log(n)) |
| into sorted | Beap::into_sorted_vec |
O(n*log(n)) |
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);
// You can check if an item is contained in the beap.
assert!(beap.contains(&2));
// Or get mutable access to it:
let idx = beap.index(&2).unwrap();
{
let mut val = beap.get_mut(idx).unwrap();
assert_eq!(*val, 2);
*val = 20;
}
assert_eq!(beap.peek(), Some(&20));
// 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(20));
assert_eq!(beap.pop(), Some(5));
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]);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);use beap::Beap;
let beap = Beap::from([5, 3, 1, 7]);
assert_eq!(beap.into_sorted_vec(), vec![1, 3, 5, 7]);The charts below shows the results of Beap<i64> vs BinaryHeap<i64> vs BTreeSet<i64> benches.
5 scenarios were tested:
- Sequential
pushcalls - Sequential
push+peekcalls - Sequential
push+tail(search for min) calls - Call
containsfor each value in the collection - Sequential
popcalls
each with 100, 1000 and 10000 elements.
To summarize, in some usage scenarios, Beap may be preferable,
but most often it is worth choosing BinaryHeap or BTreeSet depending on the task.
If you have any comments or suggestions, or you suddenly found an error, please start a new issue or pool request.