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 priority, 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

Operations

| 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(nlog(n)) | | merge | Beap::append | *O(nlog(n)) | | into sorted | Beap::into_sorted_vec | *O(nlog(n*)) |

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

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

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

Benchmarks

The charts below shows the results of Beap<i64> vs BinaryHeap<i64> vs BTreeSet<i64> benches.

5 scenarios were tested:

1. Sequential push calls
2. Sequential push + peek calls
3. Sequential push + tail (search for min) calls
4. Call contains for each value in the collection
5. Sequential pop calls

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.