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 std::{collections::HashSet, sync::Arc};
 
use axum::{
    body::Body,

Feature-flag middleware in Axum

middleware async shared-state
Advanced 7 steps
rust 
pub fn format_size(bytes: u64) -> String {
    const UNITS: [&str; 7] = ["B", "KiB", "MiB", "GiB", "TiB", "PiB", "EiB"];
 
    if bytes < 1024 {

Formatting byte counts as human-readable sizes

bit-manipulation formatting unit-conversion
Intermediate 5 steps
rust 
use base64::engine::general_purpose::{STANDARD, URL_SAFE_NO_PAD};
use base64::{DecodeError, Engine};
 
pub fn encode_standard(data: &[u8]) -> String {

Base64 encode and decode in Rust

base64 encoding error-handling
Beginner 7 steps
rust 
use std::collections::HashMap;
 
#[derive(Debug)]
pub struct RequestHead {

Parsing an HTTP request head in Rust

parsing error-handling iterators
Intermediate 9 steps
rust 
#[derive(Debug, Default)]
pub struct RequestBuilder {
    url: String,
    method: String,

The builder pattern in Rust

builder-pattern method-chaining ergonomic-api
Intermediate 8 steps
java 
package com.example.lb;
 
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

A thread-safe round-robin load balancer in Java

concurrency load-balancing round-robin
Intermediate 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