[−][src]Crate dary_heap
A priority queue implemented with a dary 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 dary heap can be done inplace, and has O(n) complexity. A dary heap can also be converted to a sorted vector inplace, allowing it to be used for an O(n * log(n)) inplace heapsort.
Comparison to standard library
The standard library contains a 2ary heap
(std::collections::BinaryHeap
). The BinaryHeap
of this crate
aims to be a dropin replacement, both in API and in performance. Cargo
features are used in place of unstable Rust features. The advantage of this
crate over the standard library lies in the possibility of easily changing
the arity of the heap, which can increase performance.
Comparison of different arities d
The arity d is defined as the maximum number of children each node can
have. A higher number means the heap has less layers, but may require more
work per layer because there are more children present. This generally makes
methods adding elements to the heap such as push
faster, and methods
removing them such as pop
slower. However, due to higher cache locality
for higher d, the drop in pop
performance is often diminished. If you're
unsure what value of d to choose, the QuaternaryHeap
with d = 4 is
usually a good start, but benchmarking is necessary to determine the best
value of d.
Usage
Rust type interference cannot infer the desired heap arity (value of d)
automatically when using DaryHeap
directly. It is therefore more
ergonomic to use one of the type aliases to select the desired arity:
Name  Arity 

BinaryHeap  d = 2 
TernaryHeap  d = 3 
QuaternaryHeap  d = 4 
QuinaryHeap  d = 5 
SenaryHeap  d = 6 
SeptenaryHeap  d = 7 
OctonaryHeap  d = 8 
The difference in ergonomics illustrated in the following:
use dary_heap::{DaryHeap, D3, TernaryHeap}; // Type parameter T can be inferred, but arity cannot let mut heap1 = DaryHeap::<_, D3>::new(); heap1.push(42); // Type alias removes need for explicit type let mut heap2 = TernaryHeap::new(); heap2.push(42);
If a different arity is desired, you can use the arity
macro or
implement the necessary trait Arity
yourself. It should be noted that
d > 8 is rarely beneficial.
use dary_heap::{arity, DaryHeap}; arity! { pub(crate) D9 = 9; } pub(crate) type NovenaryHeap<T> = DaryHeap<T, D9>;
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 DaryHeap
with custom types.
use std::cmp::Ordering; use dary_heap::TernaryHeap; #[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 minheap // instead of a maxheap. 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 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 memoryefficient 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 = TernaryHeap::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 (minheap) 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 oneway. // // 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); }
Macros
arity  Convenience macro to implement 
Structs
DaryHeap  A priority queue implemented with a dary heap. 
Drain  A draining iterator over the elements of a 
DrainSorted  A draining iterator over the elements of a 
IntoIter  An owning iterator over the elements of a 
IntoIterSorted  
Iter  An iterator over the elements of a 
PeekMut  Structure wrapping a mutable reference to the greatest item on a

Enums
D2  Marker for arity d = 2. 
D3  Marker for arity d = 3. 
D4  Marker for arity d = 4. 
D5  Marker for arity d = 5. 
D6  Marker for arity d = 6. 
D7  Marker for arity d = 7. 
D8  Marker for arity d = 8. 
Traits
Arity  Marker to specify arity d in a dary heap. 
Type Definitions
BinaryHeap  A binary heap (d = 2). 
OctonaryHeap  An octonary heap (d = 8). 
QuaternaryHeap  A quaternary heap (d = 4). 
QuinaryHeap  A quinary heap (d = 5). 
SenaryHeap  A senary heap (d = 6). 
SeptenaryHeap  A septenary heap (d = 7). 
TernaryHeap  A ternary heap (d = 3). 