Module std::collections::binary_heap [] [src]

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; use std::usize; #[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: &State) -> Ordering { // Notice that the we flip the ordering here other.cost.cmp(&self.cost) } } // `PartialOrd` needs to be implemented as well. impl PartialOrd for State { fn partial_cmp(&self, other: &State) -> Option<Ordering> { Some(self.cmp(other)) } } // Each node is represented as an `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) -> 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 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 usize::MAX } 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), 1); assert_eq!(shortest_path(&graph, 0, 3), 3); assert_eq!(shortest_path(&graph, 3, 0), 7); assert_eq!(shortest_path(&graph, 0, 4), 5); assert_eq!(shortest_path(&graph, 4, 0), usize::MAX); }
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::usize;

#[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: &State) -> Ordering {
        // Notice that the we flip the ordering here
        other.cost.cmp(&self.cost)
    }
}

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

// Each node is represented as an `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) -> 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 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
    usize::MAX
}

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), 1);
    assert_eq!(shortest_path(&graph, 0, 3), 3);
    assert_eq!(shortest_path(&graph, 3, 0), 7);
    assert_eq!(shortest_path(&graph, 0, 4), 5);
    assert_eq!(shortest_path(&graph, 4, 0), usize::MAX);
}

Structs

BinaryHeap

A priority queue implemented with a binary heap.

Drain

An iterator that drains a BinaryHeap.

IntoIter

An iterator that moves out of a BinaryHeap.

Iter

BinaryHeap iterator.