#binary #heap #priority #queue

binary-heap-plus

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

12 unstable releases (3 breaking)

0.4.1 Jan 6, 2021
0.4.0 Sep 29, 2020
0.3.1 Sep 24, 2020
0.3.0 Jul 8, 2020
0.1.4 May 18, 2018

#69 in Data structures

Download history 6365/week @ 2022-03-12 9937/week @ 2022-03-19 10269/week @ 2022-03-26 8872/week @ 2022-04-02 9885/week @ 2022-04-09 8068/week @ 2022-04-16 7525/week @ 2022-04-23 10994/week @ 2022-04-30 10633/week @ 2022-05-07 7463/week @ 2022-05-14 8090/week @ 2022-05-21 6134/week @ 2022-05-28 7712/week @ 2022-06-04 8587/week @ 2022-06-11 7282/week @ 2022-06-18 6677/week @ 2022-06-25

31,347 downloads per month
Used in 15 crates (10 directly)

MIT license

67KB
787 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.

MSRV (Minimum Supported Rust Version)

This crate requires Rust 1.32.0 or later.

Changes

See CHANGELOG.md. https://github.com/sekineh/binary-heap-plus-rs/blob/master/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 optimazation.

References

See the following discussions for the background of the crate:

Dependencies

~185KB