二叉堆

• 文档
• 包

描述

使用二叉堆实现的高级队列。

Beap（二叉堆）是一个隐式数据结构，它允许高效地插入和搜索元素，开销低（O(1)）。

插入和弹出最大元素的时间复杂度为O(sqrt(2n))。检查最大元素是O(1)。将向量转换为beap可以通过排序完成，具有O(nlog(n))时间复杂度。尽管与经典二叉堆相比，插入和弹出操作较慢，但二叉堆有一个重要的优点：搜索和删除任意元素以及找到最小元素，其渐进复杂度为O(sqrt(2n))，而二叉堆为O(n)。

本包提供了一个二叉堆的实现——Beap，它与来自 std::collections 的 BinaryHeap 具有相同的接口，同时它还具有几个新功能。

了解二叉堆

• 维基百科

用法

作为库

use beap::Beap;

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

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

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

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

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

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

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

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

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

已知项目列表的 Beap 可以从数组初始化

use beap::Beap;
let beap = Beap::from([1, 5, 2]);

最小堆

可以使用 core::cmp::Reverse 或自定义 Ord 实现将 Beap 转换为最小堆。这使得 beap.pop() 返回最小值而不是最大值。

use beap::Beap;
use std::cmp::Reverse;

let mut beap = Beap::new();

// Wrap values in `Reverse`
beap.push(Reverse(1));
beap.push(Reverse(5));
beap.push(Reverse(2));

// If we pop these scores now, they should come back in the reverse order.
assert_eq!(beap.pop(), Some(Reverse(1)));
assert_eq!(beap.pop(), Some(Reverse(2)));
assert_eq!(beap.pop(), Some(Reverse(5)));
assert_eq!(beap.pop(), None);

排序

use beap::Beap;

let beap = Beap::from([5, 3, 1, 7]);
assert_eq!(beap.into_sorted_vec(), vec![1, 3, 5, 7]);

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