binary-heap-plus-rs

Enhancement over Rust's std::collections::BinaryHeap.

This crate requires Rust 1.26 or later.

It is a prototype that implements the following variations in a backward-compatible way.

• The suffix _min refers to min heap.
• The suffix _by and _by_key are analogous to sort_by and sort_by_key.

::new_xxx()

• ::new() // creates a max heap
• ::new_min() // creates a min heap
• ::new_by(f) // creates a heap ordered by the given closure f
• ::new_by_key(g) // creates a heap ordered by key generated by the given closure g

::with_capacity_xxx()

• ::with_capacity(n) // creates a max heap with capacity n
• ::with_capacity_min(n) // creates a min heap with capacity n
• ::with_capacity_by(n, f) // creates a heap with capacity n, ordered by the given closure f
• ::with_capacity_by_key(n, g) // creates a heap with capacity n, ordered by key generated by the given closure g

Future

In future, the trait Compare<T> might be replaced with FnMut(&T, &T) -> Ordering.

To do that, rustc needs to stabilize a few unstable features.

References

See the following discussions for the background: - https://internals.rust-lang.org/t/pre-rfc-binaryheap-flexibility/7482 - https://users.rust-lang.org/t/binaryheap-flexibility-revisited-supporting-other-than-max-heap/17062 - https://users.rust-lang.org/t/binaryheap-flexibility/8766 - https://github.com/rust-lang/rust/issues/38886