Struct TournamentTree 

pub struct TournamentTree<I, T>
where
    I: Iterator<Item = T>,
    T: Ord + Clone,
{ /* private fields */ }

Tournament Tree for K-way merge of sorted iterators

Usage Example

let iters = vec![
    vec![1, 4, 7].into_iter().peekable(),
    vec![2, 5, 8].into_iter().peekable(),
    vec![3, 6, 9].into_iter().peekable(),
];
let mut tree = TournamentTree::new(iters);

while let Some((source_idx, value)) = tree.pop() {
    println!("Source {}: {}", source_idx, value);
}
// Outputs: 1, 2, 3, 4, 5, 6, 7, 8, 9 (in order)

Implementations

impl<I, T> TournamentTree<I, T>

where I: Iterator<Item = T>, T: Ord + Clone,

pub fn new(iters: Vec<I>) -> Self

Create a new tournament tree from K iterators

Time complexity: O(K)

pub fn pop(&mut self) -> Option<(usize, T)>

Get the next minimum element

Returns (source_index, element) or None if all sources exhausted. Time complexity: O(log K)

pub fn peek(&mut self) -> Option<(usize, &T)>

Peek at the next minimum element without consuming it

pub fn is_empty(&self) -> bool

Check if all sources are exhausted

pub fn source_count(&self) -> usize

Get the number of sources