# Module std::collections::binary_heap

1.0.0 · source ·
Expand description

A priority queue implemented with a binary heap.

Insertion and popping the largest element have O(log(n)) time complexity. Checking the largest element is O(1). Converting a vector to a binary heap can be done in-place, and has O(n) complexity. A binary heap can also be converted to a sorted vector in-place, allowing it to be used for an O(n * log(n)) in-place heapsort.

## Examples

This is a larger example that implements Dijkstra’s algorithm to solve the shortest path problem on a directed graph. It shows how to use `BinaryHeap` with custom types.

    use std::cmp::Ordering;
    use std::collections::BinaryHeap;

    #[derive(Copy, Clone, Eq, PartialEq)]
    struct State {
        cost: usize,
        position: usize,
    }

    // The priority queue depends on `Ord`.
    // Explicitly implement the trait so the queue becomes a min-heap
    // instead of a max-heap.
    impl Ord for State {
        fn cmp(&self, other: &Self) -> Ordering {
            // Notice that the we flip the ordering on costs.
            // In case of a tie we compare positions - this step is necessary
            // to make implementations of `PartialEq` and `Ord` consistent.
            other.cost.cmp(&self.cost)
                .then_with(|| self.position.cmp(&other.position))
        }
    }

    // `PartialOrd` needs to be implemented as well.
    impl PartialOrd for State {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }

    // Each node is represented as a `usize`, for a shorter implementation.
    struct Edge {
        node: usize,
        cost: usize,
    }

    // Dijkstra's shortest path algorithm.

    // Start at `start` and use `dist` to track the current shortest distance
    // to each node. This implementation isn't memory-efficient as it may leave duplicate
    // nodes in the queue. It also uses `usize::MAX` as a sentinel value,
    // for a simpler implementation.
    fn shortest_path(adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {
        // dist[node] = current shortest distance from `start` to `node`
        let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect();

        let mut heap = BinaryHeap::new();

        // We're at `start`, with a zero cost
        dist[start] = 0;
        heap.push(State { cost: 0, position: start });

        // Examine the frontier with lower cost nodes first (min-heap)
        while let Some(State { cost, position }) = heap.pop() {
            // Alternatively we could have continued to find all shortest paths
            if position == goal { return Some(cost); }

            // Important as we may have already found a better way
            if cost > dist[position] { continue; }

            // For each node we can reach, see if we can find a way with
            // a lower cost going through this node
            for edge in &adj_list[position] {
                let next = State { cost: cost + edge.cost, position: edge.node };

                // If so, add it to the frontier and continue
                if next.cost < dist[next.position] {
                    heap.push(next);
                    // Relaxation, we have now found a better way
                    dist[next.position] = next.cost;
                }
            }
        }

        // Goal not reachable
        None
    }

    fn main() {
        // This is the directed graph we're going to use.
        // The node numbers correspond to the different states,
        // and the edge weights symbolize the cost of moving
        // from one node to another.
        // Note that the edges are one-way.
        //
        //                  7
        //          +-----------------+
        //          |                 |
        //          v   1        2    |  2
        //          0 -----> 1 -----> 3 ---> 4
        //          |        ^        ^      ^
        //          |        | 1      |      |
        //          |        |        | 3    | 1
        //          +------> 2 -------+      |
        //           10      |               |
        //                   +---------------+
        //
        // The graph is represented as an adjacency list where each index,
        // corresponding to a node value, has a list of outgoing edges.
        // Chosen for its efficiency.
        let graph = vec![
            // Node 0
            vec![Edge { node: 2, cost: 10 },
                 Edge { node: 1, cost: 1 }],
            // Node 1
            vec![Edge { node: 3, cost: 2 }],
            // Node 2
            vec![Edge { node: 1, cost: 1 },
                 Edge { node: 3, cost: 3 },
                 Edge { node: 4, cost: 1 }],
            // Node 3
            vec![Edge { node: 0, cost: 7 },
                 Edge { node: 4, cost: 2 }],
            // Node 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);
    }

Run

## Structs

- DrainSorted Experimental
  A draining iterator over the elements of a `BinaryHeap`.
- IntoIterSorted Experimental
- BinaryHeap
  A priority queue implemented with a binary heap.
- Drain
  A draining iterator over the elements of a `BinaryHeap`.
- IntoIter
  An owning iterator over the elements of a `BinaryHeap`.
- Iter
  An iterator over the elements of a `BinaryHeap`.
- PeekMut
  Structure wrapping a mutable reference to the greatest item on a `BinaryHeap`.