binary-heap-plus-rs

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

It supports the following features and still maintains backward compatibility.

• Max heap
• Min heap
• Heap ordered by closure
• Heap ordered by key generated by closure

You can change the line

use std::collections::BinaryHeap;

to like below.

use binary_heap_plus::*;

Your code will compile as before unless you use unstable APIs.

This crate requires Rust 1.26 or later.

Added muthods

BinaryHeap::new_xxx()

• (original) ::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

BinaryHeap::with_capacity_xxx()

• (original) ::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.

Thanks

• I received many valuable feedback from Pre-RFC thread [1].
  • The current design is based on @ExpHP's suggestion that compiles on stable compiler.
  • DDOtten, steven099, CAD97, ExpHP, scottmcm, Nemo157 and gnzlbg, thanks for looking into the design!
• @ulysseB sent me a first pull request!

References

See the following discussions for the background of the crate:

• [1] 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
• rust-lang/rust#38886