Skip to main content

Top-K with a Bounded Heap

Challenge on lesson: Checkpoint: Streaming Top-K

The streaming-top-K problem: keep the K largest values seen, using a MIN-heap of size K. The boilerplate declares: ``c #define K 5 typedef struct { long a[K]; size_t n; } TopK; void tk_init(TopK *t); /* offer one value; the heap keeps the K largest seen so far. 0 ok, -1 NULL. Always O(log K). */ int tk_offer(TopK *t, long v); /* fills out (size K) with the current K largest in DESCENDING order (out[0] = largest). Returns the count filled (== t->n, may be < K). */ size_t tk_report(const TopK *t, long *out); size_t tk_size(const TopK *t); ``

Difficulty: intermediate

Back to lesson: Checkpoint: Streaming Top-K