PriorityQueue

此crate实现了一个具有更改对象优先级功能的优先队列。优先级和项目存储在IndexMap中，队列作为索引堆实现。

请在此处阅读API 文档

使用方法

要使用此crate，只需将以下字符串添加到您的Cargo.toml

priority-queue = "2.0.0"

或使用以下命令cargo add priority-queue

版本号遵循semver约定。

然后在您的Rust源代码中使用数据结构，如下例所示。

请记住，如果您需要serde支持，应使用--features serde进行编译。

示例

use priority_queue::PriorityQueue;

fn main() {
    let mut pq = PriorityQueue::new();

    assert!(pq.is_empty());
    pq.push("Apples", 5);
    pq.push("Bananas", 8);
    pq.push("Strawberries", 23);

    assert_eq!(pq.peek(), Some((&"Strawberries", &23)));

    for (item, _) in pq.into_sorted_iter() {
        println!("{}", item);
    }
}

默认情况下，将首先提取优先级最高的元素。可以使用标准包装器轻松反转顺序Reverse<T>。

use priority_queue::PriorityQueue;
use std::cmp::Reverse;

fn main() {
    let mut pq = PriorityQueue::new();

    assert!(pq.is_empty());
    pq.push("Apples", Reverse(5));
    pq.push("Bananas", Reverse(8));
    pq.push("Strawberries", Reverse(23));

    assert_eq!(pq.peek(), Some((&"Apples", &Reverse(5))));

    for (item, _) in pq.into_sorted_iter() {
        println!("{}", item);
    }
}

加速

您可以使用自定义BuildHasher对底层的IndexMap进行操作，从而获得更好的性能。例如，您可以使用快速的FxHash散列器创建队列

use hashbrown::hash_map::DefaultHashBuilder;

let mut pq = PriorityQueue::<_, _, DefaultHashBuilder>::with_default_hasher();

注意：FxHash不提供任何针对dos攻击的保护。这意味着某些病理输入可能会使hashmap的操作达到O(n^2)。如果无法控制输入，请使用标准散列器。

基准测试

已运行一些基准测试，以比较此优先队列与标准BinaryHeap的性能，同时使用FxHash散列器。在Ryzen 9 3900X上，基准测试产生了以下结果

test benchmarks::priority_change_on_large_double_queue     ... bench:          25 ns/iter (+/- 1)
test benchmarks::priority_change_on_large_double_queue_fx  ... bench:          21 ns/iter (+/- 1)
test benchmarks::priority_change_on_large_queue            ... bench:          15 ns/iter (+/- 0)
test benchmarks::priority_change_on_large_queue_fx         ... bench:          11 ns/iter (+/- 0)
test benchmarks::priority_change_on_large_queue_std        ... bench:     190,345 ns/iter (+/- 4,976)
test benchmarks::priority_change_on_small_double_queue     ... bench:          26 ns/iter (+/- 0)
test benchmarks::priority_change_on_small_double_queue_fx  ... bench:          20 ns/iter (+/- 0)
test benchmarks::priority_change_on_small_queue            ... bench:          15 ns/iter (+/- 0)
test benchmarks::priority_change_on_small_queue_fx         ... bench:          10 ns/iter (+/- 0)
test benchmarks::priority_change_on_small_queue_std        ... bench:       1,694 ns/iter (+/- 21)
test benchmarks::push_and_pop                              ... bench:          31 ns/iter (+/- 0)
test benchmarks::push_and_pop_double                       ... bench:          31 ns/iter (+/- 0)
test benchmarks::push_and_pop_double_fx                    ... bench:          24 ns/iter (+/- 1)
test benchmarks::push_and_pop_fx                           ... bench:          26 ns/iter (+/- 0)
test benchmarks::push_and_pop_min_on_large_double_queue    ... bench:         101 ns/iter (+/- 2)
test benchmarks::push_and_pop_min_on_large_double_queue_fx ... bench:          98 ns/iter (+/- 0)
test benchmarks::push_and_pop_on_large_double_queue        ... bench:         107 ns/iter (+/- 2)
test benchmarks::push_and_pop_on_large_double_queue_fx     ... bench:         106 ns/iter (+/- 2)
test benchmarks::push_and_pop_on_large_queue               ... bench:          84 ns/iter (+/- 1)
test benchmarks::push_and_pop_on_large_queue_fx            ... bench:          78 ns/iter (+/- 2)
test benchmarks::push_and_pop_on_large_queue_std           ... bench:          71 ns/iter (+/- 1)
test benchmarks::push_and_pop_std                          ... bench:           4 ns/iter (+/- 0)

使用标准队列更改优先级的方法如下

pq = pq.drain().map(|Entry(i, p)| {
    if i == 50_000 {
        Entry(i, p/2)
    } else {
        Entry(i, p)
    }
}).collect()

基准测试的解释是，此crate提供的数据结构通常比标准Binary Heap略慢。

在小型队列（小于10000个元素）中，使用上述代码从标准二叉堆中获得的change_priority函数，其性能远低于PriorityQueue和DoublePriorityQueue提供的函数。随着队列变大，PriorityQueue和DoublePriorityQueue的操作时间几乎相同，而标准队列的操作时间则会越来越长。

此外，随机弹出最小或最大元素的能力也带来了一定的代价，这在DoublePriorityQueue的所有操作中都有所体现，其速度低于PriorityQueue的相应操作。

贡献

请随时通过pull requests和/或issues来为此项目做出贡献。

所有贡献都必须符合与GNU LGPL版本3或任何后续版本以及MPL版本2.0兼容的许可协议。

变更

• 2.1.0 实现drain和reserve变体
• 2.0.3 一些与许可相关的维护工作
• 2.0.2 修复docs.rs构建
• 2.0.1 文档改进
• 2.0.0 本版本包含破坏性变更
  • 一些方法现在需要H: BuildHasher特质约束。这个变更可能会带来微小的影响，或者没有影响。
  • 标准库支持不再自动检测。默认功能集中已包含"std"功能，或者可以像其他Cargo功能一样启用。需要支持no_std目标的用户必须禁用默认功能。
• 1.4.0 改进shrink_to_fit，使其也能缩小内部IndexMap（#50）
• 1.3.2 修复log2_fast内部函数的bug
• 1.3.1 修复bug：[https://github.com/garro95/priority-queue/issues/42](https://github.com/garro95/priority-queue/issues/42)
• 1.3.0 从change_priority_by返回bool类型（合并#41）
• 1.2.3 进一步的性能优化（主要针对DoublePriorityQueue）
• 1.2.2 性能优化
• 1.2.1 修复bug：[https://github.com/garro95/priority-queue/issues/34](https://github.com/garro95/priority-queue/issues/34)
• 1.2.0 实现 DoublePriorityQueue 数据结构
• 1.1.1 将文档转换为Markdown格式
• 1.1.0 简化一些方法对Q: Sized的要求（修复From和FromIterator现在可以接受自定义哈希器 -- 破坏性变更：每个使用from和from_iter的场合都必须指定某种类型以帮助类型推导。为了使用默认的哈希器（RandomState），通常只需添加以下内容

    let pq: PriorityQueue<_, _> = PriorityQueue::from...
  

  或者你可以添加一个类型定义，例如

    type Pq<I, P> = PriorityQueue<I, P>
  

  然后使用 Pq::from() 或 Pq::from_iter()

• 支持无标准库架构

• 添加一个方法来移除任意位置的元素

• 移除 take_mut 依赖项 -- 破坏性变更： change_priority_by 的签名已更改。现在它接受一个优先级设置器 F: FnOnce(&mut P)。如果您愿意，可以使用不安全的 take_mut 或也使用 std::mem::replace