priq

使用原始二叉堆实现的优先队列（最小/最大堆）。

PriorityQueue 使用原始数组进行构建，以提高性能。

以下两点使这个 PriorityQueue 与其他现有的二叉堆实现不同

1 - 允许使用 PartialOrd 对数据进行排序。 - 其他所有最小-最大堆都需要对分数进行 完全排序（例如，应实现 Ord 特性）。这可能会成为一个问题，例如，当你想要根据浮点分数对项目进行排序时，这些分数没有实现 Ord 特性。 - 由于部分排序，不可比较的值被放在队列的末尾。只有在所有可比较的元素都被 pop 后，才会看到不可比较的值。 - 你可以在这里了解更多关于 Rust 实现 Ord、PartialOrd 以及它们之间区别的信息 这里

2 - 将分数和要存储的项目分开。 - 这使得关联项目实现任何排序变得更容易。 - 使评估项目的顺序变得更加容易。

3 - 具有相同分数的项目存储在第一个可用的空闲空间中。 - 这为大量条目提供了性能提升。

4 - 易于使用！

你可以在我的博客 上 阅读更多关于这个软件包的信息

实现

具有为 score 和相关 item 定义的参数的最小-最大堆！

Default 实现是一个最小堆，其中顶节点（根）是得分最低的元素

                    10
                   /  \
                58      70
               /  \    /  \
             80   92  97   99

父节点的值小于其子节点。

每个父节点，包括顶节点（根节点），都小于或等于其右子节点。

PriorityQueue 允许重复的分数/项目值。当你使用具有相似分数的项目放入队列时，新条目将存储在内存中的第一个空位置。这提供了增量性能提升（而不是通过使用关联项目作为优先级评估的次要工具来解决）。此外，这种实现形式不强制要求元素 T 实现任何排序。这保证了顶节点始终是值最小的。

您可以初始化一个空的 PriorityQueue，然后添加项目

use priq::PriorityQueue;

// create queue with `usize` key and `String` elements
let pq: PriorityQueue<usize, String> = PriorityQueue::new();

或者您可以对 Vec 和/或 slice 进行 堆化

use priq::PriorityQueue;

let pq_from_vec = PriorityQueue::from(vec![(5, 55), (1, 11), (4, 44)]);
let pq_from_slice = PriorityQueue::from([(5, 55), (1, 11), (4, 44)]);

部分排序

因为 priq 允许只实现 PartialOrd 的 score 参数，所以无法比较的元素将被评估并放在队列的后面

use priq::PriorityQueue;

let mut pq: PriorityQueue<f32, isize> = PriorityQueue::new();

pq.put(1.1, 10);
pq.put(f32::NAN, -1);
pq.put(2.2, 20);
pq.put(3.3, 30);
pq.put(f32::NAN, -3);
pq.put(4.4, 40);

(1..=4).for_each(|i| assert_eq!(i * 10, pq.pop().unwrap().1));

// NAN scores will not have deterministic order
// they are just stored after all the comparable scores
assert!(0 > pq.pop().unwrap().1);
assert!(0 > pq.pop().unwrap().1);

时间复杂度

此数据结构的标准用法是将元素 put 到队列中，并 pop 以删除队列顶部的元素，并检查队列顶部的元素。存储的元素结构是通过使用具有连续内存位置的数组实现的平衡树。这允许维护放入元素之间的正确父子关系。

大O符号的时间复杂度

您也可以使用循环遍历元素，但返回的切片将不会正确排序，因为每次插入和删除后堆都会重新平衡。如果您想以正确的优先级获取项目，请在循环中调用 pop 直到它返回 None。

自定义 struct

如果您想要自定义 struct 而不是有一个独立的和特定的分数，您可以传递 struct 的克隆作为 score 和相关值，但在这种情况下，我建议使用 BinaryHeap，因为它更适合目的。

最小堆

如果您想要最大堆而不是最小堆，其中最高分的元素在顶部，您可以使用 Reverse 或自定义 [Ord] 实现来具有自定义的优先级逻辑。

示例

use priq::PriorityQueue;
use std::cmp::Reverse;

let mut pq: PriorityQueue<Reverse<u8>, String> = PriorityQueue::new();

pq.put(Reverse(26), "Z".to_string());
pq.put(Reverse(1), "A".to_string());

assert_eq!(pq.pop().unwrap().1, "Z");

合并和组合

您可以将另一个优先级队列合并到这个队列中。右侧的优先级队列将排空到左侧的优先级队列中。

示例

use priq::PriorityQueue;

let mut pq1 = PriorityQueue::from([(5, 55), (6, 66), (3, 33), (2, 22)]);
let mut pq2 = PriorityQueue::from([(4, 44), (1, 11)]);

pq1.merge(&mut pq2);
// at this point `pq2` is empty

assert_eq!(6, pq1.len());
assert_eq!(11, pq1.peek().unwrap().1);

您还可以使用 + 运算符合并两个优先级队列。操作数将保持不变。新优先级队列将通过克隆和合并它们来构建。

示例

use priq::PriorityQueue;

let pq1 = PriorityQueue::from([(5, 55), (1, 11), (4, 44), (2, 22)]);
let pq2 = PriorityQueue::from([(8, 44), (1, 22)]);

let res = pq1 + pq2;

assert_eq!(6, res.len());
assert_eq!(11, res.peek().unwrap().1);

性能

这是 priq::PriorityQueue 的基准测试结果

与 std::collections::BinaryHeap 的比较

项目是在 MIT 许可下分发的。有关更多信息，请参阅 LICENSE。