Weak Heap

• 文档
• 包

描述

使用弱堆实现的优先队列。

插入和弹出最大元素的时间复杂度为 O(log(n))。检查最大元素的时间复杂度为 O(1)。将向量转换为弱堆可以在原地完成，且具有 O(n) 复杂度。弱堆也可以在原地转换为排序后的向量，允许它用于 O(n * log(n)) 的就地弱堆排序。

使用弱堆的主要目的是最小化 push 和 pop 操作或排序所需的比较次数，因此在比较元素代价高昂的情况下特别有用，例如字符串排序。对于经典的数字比较，仍然建议使用标准二叉堆，因为与常规二叉堆相比，弱堆的操作需要额外的数值运算。

此包提供了一个弱堆的实现 - WeakHeap，它与 std::collections 中的 BinaryHeap 具有相同的接口，并且同时具有几个新有用的方法。

了解弱堆

• 维基百科
• 弱堆数据结构：变体和应用程序

用法

作为库

use weakheap::WeakHeap;

// Type inference lets us omit an explicit type signature (which
// would be `WeakHeap<i32>` in this example).
let mut heap = WeakHeap::new();

// We can use peek to look at the next item in the heap. In this case,
// there's no items in there yet so we get None.
assert_eq!(heap.peek(), None);

// Let's add some scores...
heap.push(1);
heap.push(5);
heap.push(2);

// Now peek shows the most important item in the heap.
assert_eq!(heap.peek(), Some(&5));

// We can check the length of a heap.
assert_eq!(heap.len(), 3);

// We can iterate over the items in the heap, although they are returned in
// a random order.
for x in heap.iter() {
   println!("{}", x);
}

// If we instead pop these scores, they should come back in order.
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);

// We can clear the heap of any remaining items.
heap.clear();

// The heap should now be empty.
assert!(heap.is_empty())

基准测试

所有测试均使用相同的数据 - 小说的摘录中的单词。`input` 轴显示在此基准中使用的行数。`Append` 操作是两个堆的合并。

从提供的图表中可以看出，当元素是字符串时，弱堆比二叉堆工作得更快，然而，由 Rust 中的 `Vec::sort_unstable` 方法实现的快速排序算法在排序方面表现得最好。

如果您有任何评论或建议，或者您突然发现了一个错误，请发起一个新的问题或拉取请求。