#binary-heap #heap #binary #queue #priority #priority-queue

dotreds-binary-heap-plus

Enhanced version of std::collections::BinaryHeap that supports max, min, and custom-order heaps. Makes some previously internal function public

5 releases (stable)

1.0.3 Apr 21, 2022
0.4.1 Apr 21, 2022

#1783 in Data structures

MIT license

25KB
538 lines

binary-heap-plus-rs

Rust

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

This version of Binary-heap-plus makes some private functions public.

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

~20KB