Module alloc::collections::binary_heap
1.0.0 · source · Expand description
用二进制堆实现的优先级队列。
插入和弹出最大元素具有 O(log(n)) 时间复杂度。 检查最大的元素是 O(1)。可以就地将 vector 转换为二进制堆,并且复杂度为 O(n)。 二元堆也可以就地转换为已排序的 vector,允许它用于 O(n * log(n)) 就地堆排序。
Examples
这是一个较大的示例,实现了 Dijkstra 算法 来解决 有向图 上的 最短路径问题。
它显示了如何将 BinaryHeap
与自定义类型一起使用。
use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
cost: usize,
position: usize,
}
// 优先级队列取决于 `Ord`。
// 显式实现 trait,以便队列成为最小堆而不是最大堆。
//
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
// 请注意,我们翻转了费用排序。
// 在平局的情况下,我们比较位置 - 必须执行此步骤才能使 `PartialEq` 和 `Ord` 的实现保持一致。
//
other.cost.cmp(&self.cost)
.then_with(|| self.position.cmp(&other.position))
}
}
// `PartialOrd` 也需要实现。
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
// 对于较短的实现,每个节点都表示为 `usize`。
struct Edge {
node: usize,
cost: usize,
}
// Dijkstra 的最短路径算法。
// 从 `start` 开始,并使用 `dist` 跟踪到每个节点的当前最短距离。此实现的内存效率不高,因为它可能会将重复的节点留在队列中。
//
// 它还将 `usize::MAX` 用作标记值,以实现更简单的实现。
//
fn shortest_path(adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {
// dist[node] = 当前从 `start` 到 `node` 的最短距离
let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect();
let mut heap = BinaryHeap::new();
// 我们正处于 `start` 阶段,成本为零
dist[start] = 0;
heap.push(State { cost: 0, position: start });
// 首先检查成本较低的节点的边界 (min-heap)
while let Some(State { cost, position }) = heap.pop() {
// 或者,我们可以继续找到所有最短的路径
if position == goal { return Some(cost); }
// 重要,因为我们可能已经找到了更好的方法
if cost > dist[position] { continue; }
// 对于我们可以到达的每个节点,看看是否可以找到一种成本更低的方法通过该节点
//
for edge in &adj_list[position] {
let next = State { cost: cost + edge.cost, position: edge.node };
// 如果是这样,请将其添加到边界并继续
if next.cost < dist[next.position] {
heap.push(next);
// 放松,我们现在找到了更好的方法
dist[next.position] = next.cost;
}
}
}
// 无法达成目标
None
}
fn main() {
// 这是我们将要使用的有向图。
// 节点编号对应于不同的状态,并且 edge 权重表示从一个节点移动到另一个节点的成本。
//
// 请注意,edges 是单向的。
//
// 7
// +-----------------+
// | |
// v 1 2 | 2
// 0 -----> 1 -----> 3 ---> 4
// | ^ ^ ^
// | | 1 | |
// | | | 3 | 1 +------> 2 -------+ |
// 10 | |
// +---------------+
//
// 该图表示为邻接表,其中每个索引 (对应于节点值) 具有传出 edges 的列表。
// 选择它的效率。
//
//
//
let graph = vec![
// 节点 0
vec![Edge { node: 2, cost: 10 },
Edge { node: 1, cost: 1 }],
// 节点 1
vec![Edge { node: 3, cost: 2 }],
// 节点 2
vec![Edge { node: 1, cost: 1 },
Edge { node: 3, cost: 3 },
Edge { node: 4, cost: 1 }],
// 节点 3
vec![Edge { node: 0, cost: 7 },
Edge { node: 4, cost: 2 }],
// 节点 4
vec![]];
assert_eq!(shortest_path(&graph, 0, 1), Some(1));
assert_eq!(shortest_path(&graph, 0, 3), Some(3));
assert_eq!(shortest_path(&graph, 3, 0), Some(7));
assert_eq!(shortest_path(&graph, 0, 4), Some(5));
assert_eq!(shortest_path(&graph, 4, 0), None);
}
RunStructs
- DrainSortedExperimental
BinaryHeap
的元素上的 draining 迭代器。 - IntoIterSortedExperimental
- 用二进制堆实现的优先级队列。
BinaryHeap
的元素上的 draining 迭代器。BinaryHeap
元素上的拥有的迭代器。BinaryHeap
元素上的迭代器。- 将可变引用引至
BinaryHeap
上最大部分的结构体。