Module std::collections::binary_heap

用二进制堆实现的优先级队列。

插入和弹出最大元素具有 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);
}

Structs

• DrainSortedExperimental
  BinaryHeap 的元素上的 draining 迭代器。
• IntoIterSortedExperimental
• BinaryHeap
  用二进制堆实现的优先级队列。
• Drain
  BinaryHeap 的元素上的 draining 迭代器。
• IntoIter
  BinaryHeap 元素上的拥有的迭代器。
• Iter
  BinaryHeap 元素上的迭代器。
• PeekMut
  将可变引用引至 BinaryHeap 上最大部分的结构体。