pub type PsumTree = igraph_psumtree_t;Expand description
A partial prefix-sum tree (igraph_psumtree_t): a fixed number of items,
each with a non-negative weight, supporting weight updates and
weighted sampling in O(log n).
It is the data structure igraph uses internally to draw vertices with
probability proportional to changing weights (e.g. in preferential
attachment models or in the SIR simulation).
search maps a number in [0, sum) to the item
whose cumulative weight interval contains it, so feeding it uniform
random numbers samples items proportionally to their weights; this is
what sample does.
For one-off sampling from a fixed distribution, the functions of
crate::rng are simpler; the tree pays off when weights change
between draws.
Binds the igraph_psumtree_* functions, see the
igraph manual.
§Examples
use igraph::misc::PsumTree;
let mut tree = PsumTree::from_weights(&[1.0, 0.0, 3.0])?;
assert_eq!(tree.sum(), 4.0);
// [0, 1) -> item 0; [1, 4) -> item 2 (item 1 has no weight)
assert_eq!(tree.search(0.5)?, 0);
assert_eq!(tree.search(1.0)?, 2);
tree.update(1, 10.0)?;
assert_eq!(tree.search(1.0)?, 1);
assert_eq!(tree.get(1), Some(10.0));Aliased Type§
pub struct PsumTree { /* private fields */ }