1use alloc::collections::BinaryHeap;
2use core::cmp::Ord;
3
4pub(crate) fn k_smallest<T: Ord, I: Iterator<Item = T>>(mut iter: I, k: usize) -> BinaryHeap<T> {
5 if k == 0 {
6 return BinaryHeap::new();
7 }
8
9 let mut heap: BinaryHeap = iter.by_ref().take(k).collect::<BinaryHeap<_>>();
10
11 iter.for_each(|i: T| {
12 debug_assert_eq!(heap.len(), k);
13 // Equivalent to heap.push(min(i, heap.pop())) but more efficient.
14 // This should be done with a single `.peek_mut().unwrap()` but
15 // `PeekMut` sifts-down unconditionally on Rust 1.46.0 and prior.
16 if *heap.peek().unwrap() > i {
17 *heap.peek_mut().unwrap() = i;
18 }
19 });
20
21 heap
22}
23