14 个版本
| 0.4.2 | 2022 年 2 月 20 日 |
|---|---|
| 0.4.1 | 2021 年 11 月 1 日 |
| 0.4.0 | 2021 年 10 月 24 日 |
| 0.3.8 | 2019 年 8 月 9 日 |
| 0.1.0 | 2016 年 3 月 2 日 |
#576 在 数据结构 中
每月 1,357 次下载
在 8 个crate中使用（5 直接）
26KB
641 行
radix-heap
快速单调优先队列。
单调优先队列是一种需要提取的元素遵循单调序列的优先队列。这意味着，对于最大基数堆，您不能将大于最后一个提取元素的元素插入到基数堆中。
最后一个提取元素的键称为基数堆的“顶部”键。因此，推送到堆中的任何值都必须小于或等于顶部键。
为此限制，基数堆提供了两个主要好处
-
插入是
O(1)，弹出元素的平均成本是O(log m)，其中m是弹出键与元素插入时顶部键之间的差。请注意，这与基数堆中的元素数量无关。这意味着对于这种差异受常数约束的工作负载，基数堆具有 O(1) 的弹出。
-
在基数堆中实现相同键的先进先出顺序是微不足道的。在实现路径查找时，这对应于“平局决定”，可以显著提高性能。这也可能在二叉堆中实现，但在基数堆中是免费的。
-
基数堆通常比二叉堆具有更好的缓存一致性。
性能
以下是我在机器上运行时的基准测试总结
astar_radix time: [2.6594 us 2.6622 us 2.6651 us]
astar_binary time: [5.3698 us 5.3762 us 5.3827 us]
pushpop_radix time: [97.601 us 97.784 us 97.987 us]
pushpop_binary time: [507.28 us 507.44 us 507.60 us]
astar 是使用来自 2D 路径查找基准测试 的地图的一个基准。
pushpop 是一个更注重堆的基准，其中值被重复推入和弹出堆。
示例
extern crate radix_heap;
let mut heap = radix_heap::RadixHeapMap::new();
heap.push(7, 'a');
heap.push(2, 'b');
heap.push(9, 'c');
assert!(heap.top() == None);
assert!(heap.pop() == Some((9, 'c')));
assert!(heap.top() == Some(9));
assert!(heap.pop() == Some((7, 'a')));
assert!(heap.top() == Some(7));
assert!(heap.pop() == Some((2, 'b')));
assert!(heap.top() == Some(2));
assert!(heap.pop() == None);
依赖项
~45KB