summaryrefslogtreecommitdiffstats
path: root/third_party/rust/itertools/src/k_smallest.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/itertools/src/k_smallest.rs')
-rw-r--r--third_party/rust/itertools/src/k_smallest.rs20
1 files changed, 20 insertions, 0 deletions
diff --git a/third_party/rust/itertools/src/k_smallest.rs b/third_party/rust/itertools/src/k_smallest.rs
new file mode 100644
index 0000000000..acaea5941c
--- /dev/null
+++ b/third_party/rust/itertools/src/k_smallest.rs
@@ -0,0 +1,20 @@
+use alloc::collections::BinaryHeap;
+use core::cmp::Ord;
+
+pub(crate) fn k_smallest<T: Ord, I: Iterator<Item = T>>(mut iter: I, k: usize) -> BinaryHeap<T> {
+ if k == 0 { return BinaryHeap::new(); }
+
+ let mut heap = iter.by_ref().take(k).collect::<BinaryHeap<_>>();
+
+ iter.for_each(|i| {
+ debug_assert_eq!(heap.len(), k);
+ // Equivalent to heap.push(min(i, heap.pop())) but more efficient.
+ // This should be done with a single `.peek_mut().unwrap()` but
+ // `PeekMut` sifts-down unconditionally on Rust 1.46.0 and prior.
+ if *heap.peek().unwrap() > i {
+ *heap.peek_mut().unwrap() = i;
+ }
+ });
+
+ heap
+}