From 6f798715de3d4bd744116190d14a413445542820 Mon Sep 17 00:00:00 2001 From: Joel Galenson Date: Thu, 1 Apr 2021 17:03:06 -0700 Subject: Upgrade rust/crates/itertools to 0.10.0 Test: make Change-Id: Ie8b53cb0a96fd9adcbf7f4afa3b966849fc2ff24 --- src/k_smallest.rs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 src/k_smallest.rs (limited to 'src/k_smallest.rs') 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>(mut iter: I, k: usize) -> BinaryHeap { + if k == 0 { return BinaryHeap::new(); } + + let mut heap = iter.by_ref().take(k).collect::>(); + + 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 +} -- cgit v1.2.3