dary_heap

Rust 实现了一个 d-ary 堆。当 d = 2 时，它作为 BinaryHeap 出现在标准库中，但使用更高的 d 值可以在许多用例中提高性能。这是因为更高的基数 d（每个节点可以有的最大子节点数）意味着堆包含更少的层级，使得向堆中添加元素更快。然而，删除元素较慢，因为在这种情况下，每层的作业量更高，因为子节点更多。后者的效果通常由于更高的缓存局部性而减弱。因此，当 d > 2 但不是太高时，整体性能通常会提高。对于特定用例，需要进行基准测试以确定最佳的 d 值。

兼容性和稳定性

此包的 API 目标是类似于标准库中的 BinaryHeap 的 API。标准库中的功能门控 API 在 dary_heap 中也是功能门控的，有关更多信息，请参阅功能部分。实际上，dary_heap 中的代码直接基于标准库中的代码。因此，此包提供的 BinaryHeap 应该提供与标准库类似的表现，此包提供的其他堆类型可能会提供性能改进。

此包基于的标准库版本目前为 1.70.0。目标是使包与最新的稳定 Rust 版本保持同步。

当前的最小支持 Rust 版本 (MSRV) 为 1.51.0。最后一个不带 const 泛型的版本 MSRV 为 1.31.0，并在此存储库的 非 const 泛型分支 上进行维护。

MSRV 可以在次要版本发布中进行提升，但不能在补丁级别发布中进行提升。

对于 unstable 和 unstable_nightly 功能没有稳定性保证。对零阶堆（实际上不应该使用）的行为的更改也不被视为破坏性更改，并且可以在补丁级别发布中发生。

功能

• extra：添加需要更高 MSRV（目前为 1.57.0）的功能。
  • 添加 shrink_to 方法以将堆容量缩减到较低限制。
  • 添加 try_reserve 方法，尝试在堆中预留额外容量。
  • 添加 try_reserve_exact 方法，尝试预留最小额外容量。
• serde：添加使用 Serde 进行序列化和反序列化的支持。
• unstable：启用对实验性（不稳定）特性的支持
  • 添加 as_slice 函数，以任意顺序获取底层数据的切片。
  • 添加类似于 drain 的 drain_sorted 方法，但生成堆顺序的元素。
  • 添加类似于 into_iter 的 into_iter_sorted 方法，但生成堆顺序的元素。
• unstable_nightly：启用对需要 nightly Rust 编译器的实验性（不稳定）特性的支持
  • 在此crate中实现由不稳定特性 exact_size_is_empty 定义的 ExactSizeIterator 的方法。
  • 实现由不稳定特性 extend_one 定义的的方法。
  • 为 IntoIter 实现 SourceIter 和 InPlaceIterable。
  • 如果可能，为迭代器实现 TrustedLen（仅当 unstable 也启用时）。

许可证

dary_heap 的许可证是以下之一

• Apache License, Version 2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 https://opensource.org/licenses/MIT)

任选其一。