rust 45 lines · 8 steps

Top-K selection with a bounded min-heap in Rust

Keep only the k largest elements by holding a fixed-size min-heap that evicts its smallest whenever it overflows.

Explained by highlit
Intermediate heap top-k generics algorithms ordering
1use std::collections::BinaryHeap;
2use std::cmp::Reverse;
3 
4pub fn top_k<T: Ord + Clone>(items: &[T], k: usize) -> Vec<T> {
5 if k == 0 {
6 return Vec::new();
7 }
8 
9 let mut heap: BinaryHeap<Reverse<T>> = BinaryHeap::with_capacity(k + 1);
10 
11 for item in items {
12 heap.push(Reverse(item.clone()));
13 if heap.len() > k {
14 heap.pop();
15 }
16 }
17 
18 let mut result: Vec<T> = heap.into_iter().map(|Reverse(v)| v).collect();
19 result.sort_unstable_by(|a, b| b.cmp(a));
20 result
21}
22 
23pub fn top_k_by_key<T, K, F>(items: Vec<T>, k: usize, mut key: F) -> Vec<T>
24where
25 K: Ord,
26 F: FnMut(&T) -> K,
27{
28 let mut heap: BinaryHeap<(Reverse<K>, usize)> = BinaryHeap::with_capacity(k + 1);
29 
30 for (idx, item) in items.iter().enumerate() {
31 heap.push((Reverse(key(item)), idx));
32 if heap.len() > k {
33 heap.pop();
34 }
35 }
36 
37 let mut selected: Vec<usize> = heap.into_iter().map(|(_, idx)| idx).collect();
38 selected.sort_unstable();
39 
40 let mut picked: Vec<Option<T>> = items.into_iter().map(Some).collect();
41 selected
42 .into_iter()
43 .map(|idx| picked[idx].take().unwrap())
44 .collect()
45}
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1Wrapping values in Reverse turns Rust's max-heap into a min-heap so you can cheaply evict the smallest candidate.
  2. 2Capping the heap at k gives O(n log k) selection with O(k) memory instead of sorting everything.
  3. 3Carrying original indices and taking from an Option vector lets you return owned values while preserving stable order.

Related explainers

rust 
use serde::Deserialize;
 
#[derive(Debug, Deserialize)]
#[serde(untagged)]

Parsing flexible JSON shapes with serde

deserialization enums json
Intermediate 6 steps
rust 
use std::cmp::{Ordering, Reverse};
use std::collections::BinaryHeap;
use std::fs::File;
use std::io::{self, BufRead, BufReader, BufWriter, Lines, Write};

K-way merge of sorted logs in Rust

binary-heap k-way-merge streaming-io
Intermediate 8 steps
rust 
use axum::{
    extract::{Path, State},
    response::sse::{Event, KeepAlive, Sse},
};

Streaming import progress with SSE in Axum

server-sent-events streams watch-channel
Advanced 7 steps
rust 
use std::f64::consts::PI;
 
#[derive(Debug, Clone, Copy)]
pub struct LatLng {

Building geographic bounding boxes in Rust

geospatial value-types option
Intermediate 7 steps
rust 
use chrono::{Duration, NaiveDate};
 
#[derive(Debug)]
pub struct DateRange {

Parsing and iterating date ranges in Rust

error-handling iterators parsing
Intermediate 7 steps
rust 
use std::collections::VecDeque;
use std::sync::{Arc, Condvar, Mutex};
use std::time::{Duration, Instant};
 

Building a counting semaphore in Rust

concurrency synchronization condition-variable
Advanced 9 steps

Share this explainer

Here's the card — post it anywhere.

Top-K selection with a bounded min-heap in Rust — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code