diff options
author | Joel Galenson <jgalenson@google.com> | 2021-04-01 17:03:06 -0700 |
---|---|---|
committer | Joel Galenson <jgalenson@google.com> | 2021-04-01 17:03:06 -0700 |
commit | 6f798715de3d4bd744116190d14a413445542820 (patch) | |
tree | 70e883bc01ba2b4d8dd07e0347be18a2fbbd2c18 /src/k_smallest.rs | |
parent | a06122cf145ade58c23ae76bcf31d9c748dce354 (diff) | |
download | itertools-6f798715de3d4bd744116190d14a413445542820.tar.gz |
Upgrade rust/crates/itertools to 0.10.0android-s-beta-2android-s-beta-1
Test: make
Change-Id: Ie8b53cb0a96fd9adcbf7f4afa3b966849fc2ff24
Diffstat (limited to 'src/k_smallest.rs')
-rw-r--r-- | src/k_smallest.rs | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/src/k_smallest.rs b/src/k_smallest.rs new file mode 100644 index 0000000..d58ec70 --- /dev/null +++ b/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<_>>(); + + for i in iter { + 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 +} |