Crate mut_binary_heap
source ·Expand description
This crate provides BinaryHeap that stores key-value pairs.
The main advantage of that is that unlike with an implementation like
std::collections::BinaryHeap checking if any given key exist is O(1) instead of O(n).
Same for getting the value for a given key. This allows for cheap modification of
values within the binary heap. Updating a value is O(log n) iff you have direct access to the value.
For a binary heap that does not store key-value pairs update operations would be O(n) because
they first have to find the value to update. The disadvantage is the additional storage space
required to store a HashMap that provides indices into the heap for each key.
Quick start
Max/Min Heap
Max Heap
use mut_binary_heap::*;
// max heap
let mut h: BinaryHeap<i32, i32> = BinaryHeap::new();
// max heap with initial capacity
let mut h: BinaryHeap<i32, i32> = BinaryHeap::with_capacity(42);
// max heap from iterator and key selector
let mut h: BinaryHeap<i32, i32> = BinaryHeap::from((0..42), |v| *v);
assert_eq!(h.pop(), Some(41));Min Heap
use mut_binary_heap::*;
// min heap
let mut h: BinaryHeap<i32, i32, MinComparator> = BinaryHeap::new();
// min heap with initial capacity
let mut h: BinaryHeap<i32, i32, MinComparator> = BinaryHeap::with_capacity(42);
// min heap from iterator
let mut h: BinaryHeap<i32, i32, MinComparator> = BinaryHeap::from((0..42), |v| *v);
assert_eq!(h.pop(), Some(0));Custom Heap
For custom heap, BinaryHeap::new_by() and BinaryHeap::new_by_sort_key
works in a similar way to max/min heap. The only difference is that you add
a closure returning a std::cmp::Ordering or the sort key with an apropriate signature.
use mut_binary_heap::BinaryHeap;
let mut heap = BinaryHeap::new_by_sort_key(|a: &i32| a % 4);
heap.push(0, 3);
heap.push(1, 1);
heap.push(2, 5);
assert_eq!(heap.pop(), Some(3));Constructers
Dedicated methods to create different kind of heaps
BinaryHeap::new()creates a max heap.BinaryHeap::new_min()creates a min heap.BinaryHeap::new_by()creates a heap sorted by the given closure.BinaryHeap::new_by_sort_key()creates a heap sorted by the key generated by the given closure.BinaryHeap::from()creates a max heap with the elements in the iterator and keys provided by the closure.
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 mut_binary_heap::BinaryHeap;
use std::cmp::Ordering;
#[derive(Copy, Clone, Eq, PartialEq)]
struct Node {
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 Node {
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 Node {
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.
fn shortest_path(edges: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {
let mut heap: BinaryHeap<usize, Node> = BinaryHeap::new();
heap.push(
start,
Node {
cost: 0,
position: start,
},
);
while let Some(Node { cost, position }) = heap.pop() {
if position == goal {
return Some(cost);
}
for edge in &edges[position] {
let next_cost = cost + edge.cost;
// if the edge points to a node that is already in the heap, check
// if it's cost is greater than the cost via this edge.
// Note that normally dijkstra would also have a closed list with all
// nodes that we have already visited. That closed list is also used to
// keep track of the path we have taken.
// To simplify this example we ignore that and only calculate the cost
// to the goal.
if heap.contains_key(&edge.node) {
let mut node = heap.get_mut(&edge.node).unwrap();
assert_eq!(node.position, edge.node);
if next_cost < node.cost {
node.cost = next_cost;
}
// by dropping `node` the heap is autmatically updated.
} else {
heap.push(
edge.node,
Node {
cost: next_cost,
position: edge.node,
},
);
}
}
}
// If the heap is empty, the goal wasn't found.
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);
}Structs
- A priority queue implemented with a binary heap storing key-value pairs.
- A draining iterator over the elements of a
BinaryHeap. - The comparator defined by closure
- An owning iterator over the elements of a
BinaryHeap. - The comparator ordered by key
- For
Tthat implementsOrd, you can use this struct to quickly set up a max heap. - For
Tthat implementsOrd, you can use this struct to quickly set up a min heap. - An Iterator that yields mutable references to the values in the heap. The heap will be rebuild after the iterator is droped.
- Structure wrapping a mutable reference to the first item on a
BinaryHeap. - Structure wrapping a mutable reference to any item on a
BinaryHeap.