dary_heap
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>>
forVec<T>
requires at least Rust version 1.41.0.Into<Vec<T>>
forDaryHeap<T, D>
can be used on older versions. - Support for
no_std
(but withalloc
) 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 likedrain
but yields elements in heap order. - add
into_iter_sorted
method which is likeinto_iter
but yields elements in heap order. - add
retain
function that retains only those elements in the heap specified by the predicate.
- add
unstable_nightly
: enable support for experimental (unstable) features that require a nightly Rust compiler:- implement methods defined by unstable feature
exact_size_is_empty
onExactSizeIterator
s in this crate. - implement methods defined by unstable feature
extend_one
. - implement
SourceIter
andInPlaceIterable
forIntoIter
. - add
shrink_to
method to shrink heap capacity to a lower bound. - implement
TrustedLen
for iterators if possible (only whenunstable
is also enabled).
- implement methods defined by unstable feature
License
dary_heap
is licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)
at your option.