5 releases

new 0.2.2 Jan 13, 2021
0.2.1 Nov 20, 2020
0.2.0 Oct 26, 2020
0.1.1 Oct 8, 2020
0.1.0 Sep 26, 2020

#313 in Data structures

27 downloads per month

MIT/Apache

62KB
846 lines

dary_heap

CI Crates.io Docs.rs

Rust implementation of a d-ary heap. The d = 2 version is present in the standard library as BinaryHeap, but using a higher value for d can bring performance improvements in many use cases. This is because a higher arity d (maximum number of children each node can have) means the heap contains less layers, making adding elements to the heap faster. However, removing elements is slower, because then the amount of work per layer is higher as there are more children. The latter effect is often diminished due to higher cache locality. Therefore, overall performance is often increased if d > 2 but not too high. Benchmarking is necessary to determine the best value of d for a specific use case.

Compatibility and stability

The API of this crate aims to be analogous to that of BinaryHeap in the standard library. Feature-gated API in the standard library is also feature-gated in dary_heap, see the section on features for more information. In fact, the code in dary_heap is directly based on that of the standard library. The BinaryHeap provided by this crate should therefore provide similar performance as that of the standard library, and the other heap types provided by this crate may provide performance improvements.

The version of the standard library this crate is based on is currently 1.49.0. The aim is to keep the crate in sync with the latest stable Rust release.

The minimum supported Rust version (MSRV) is currently 1.31.0. There are some minor features that depend on a higher minimum version of Rust and are automatically detected:

  • Support for From<DaryHeap<T, D>> for Vec<T> requires at least Rust version 1.41.0. Into<Vec<T>> for DaryHeap<T, D> can be used on older versions.
  • Support for no_std (but with alloc) requires at least Rust version 1.36.0.
  • Enabling the serde feature also requires at least Rust version 1.36.0.

The MSRV can be increased in a minor level release, but not in a patch level release.

There are no stability guarantees for the unstable and unstable_nightly features. Changes to the behavior of nullary heaps (that should not be used anyway) are also not considered to be breaking and can happen in a patch level release.

Features

  • serde: add support for (de)serialization using Serde.
  • unstable: enable support for experimental (unstable) features:
    • add drain_sorted method which is like drain but yields elements in heap order.
    • add into_iter_sorted method which is like into_iter but yields elements in heap order.
    • add retain function that retains only those elements in the heap specified by the predicate.
  • unstable_nightly: enable support for experimental (unstable) features that require a nightly Rust compiler:
    • implement methods defined by unstable feature exact_size_is_empty on ExactSizeIterators in this crate.
    • implement methods defined by unstable feature extend_one.
    • implement SourceIter and InPlaceIterable for IntoIter.
    • add shrink_to method to shrink heap capacity to a lower bound.
    • implement TrustedLen for iterators if possible (only when unstable is also enabled).

License

dary_heap is licensed under either of

at your option.

Dependencies

~70KB