Lib.rs

› Data structures
#priority-queue #binary-heap #heap #queue #priority #binary

binary-heap-plus

Enhanced version of std::collections::BinaryHeap that supports max, min, and custom-order heaps

by Hideki Sekine and 8 contributors

13 releases

0.5.0 Sep 30, 2022
0.4.1 Jan 6, 2021
0.4.0 Sep 29, 2020
0.3.1 Sep 24, 2020
0.1.4 May 18, 2018

#104 in Data structures

Download history 26351/week @ 2024-07-19 16013/week @ 2024-07-26 13053/week @ 2024-08-02 13252/week @ 2024-08-09 12302/week @ 2024-08-16 12441/week @ 2024-08-23 11234/week @ 2024-08-30 17992/week @ 2024-09-06 14095/week @ 2024-09-13 18826/week @ 2024-09-20 12941/week @ 2024-09-27 15429/week @ 2024-10-04 20627/week @ 2024-10-11 17718/week @ 2024-10-18 17978/week @ 2024-10-25 8229/week @ 2024-11-01

67,228 downloads per month
Used in 27 crates (18 directly)

MIT license

80KB
890 lines

binary-heap-plus-rs

Rust

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

It supports the following heaps and still maintains backward compatibility.

  • Max heap
    • Use BinaryHeap::new() or ::with_capacity()
  • Min heap
    • Use BinaryHeap::new_min() or ::with_capacity_min()
  • Heap ordered by closure
    • Use BinaryHeap::new_by() or ::with_capacity_by()
  • Heap ordered by key generated by closure
    • Use BinaryHeap::new_by_key() or ::with_capacity_by_key()

Other notable added methods are:

  • BinaryHeap::from_vec_cmp() and BinaryHeap::from_vec() for more generic construction.
  • .into_iter_sorted() which is less-surprising version of .into_iter(). The implementation is backported from std.
  • .replace_cmp() which replace the comparator of the existing heap.

Compatibility and MSRV (Minimum Supported Rust Version)

This crate is based on the standard library's implementation of BinaryHeap from Rust 1.62.0.

The minimum supported Rust version is 1.56.0.

Changes

See CHANGELOG.md.

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!
  • @inesseq contributed feature serde1.
  • @davidli2010 contributed comparator update and unsafe perf optimization.

References

See the following discussions for the background of the crate:

Dependencies

~180KB