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;
use serde_json::Value;
use std::collections::HashMap;
 

Modeling nested JSON with serde in Rust

deserialization json struct-mapping
Intermediate 9 steps
rust 
use axum::{
    body::Bytes,
    extract::State,
    http::{HeaderMap, StatusCode},

Verifying Stripe webhook signatures in Axum

hmac webhooks constant-time-comparison
Intermediate 8 steps
rust 
use axum::{
    body::Body,
    extract::Request,
    http::{header, StatusCode},

How bearer-auth middleware works in Axum

middleware authentication request extensions
Intermediate 7 steps
rust 
use std::borrow::Cow;
 
fn sanitize_filename(input: &str) -> Cow<'_, str> {
    if input.chars().all(|c| c.is_alphanumeric() || matches!(c, '.' | '-' | '_')) {

Avoiding allocations with Cow in Rust

clone-on-write borrowing zero-copy
Intermediate 7 steps
rust 
use axum::{
    http::StatusCode,
    response::IntoResponse,
    routing::get,

Serving an SPA and API with Axum

routing static-files spa-fallback
Intermediate 7 steps
rust 
use std::time::{Duration, Instant};
 
pub struct TokenBucket {
    capacity: f64,

A token bucket rate limiter in Rust

rate-limiting token-bucket lazy-refill
Intermediate 8 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