Heap-Based Solutions for Top-K and Streaming Selection

Keep the threshold, not the entire history

Suppose a stream contains millions of request latencies, but you need to retain only its largest 100 measurements. Sorting every value would require keeping the entire stream. Instead, retain 100 candidates and make the smallest retained value easy to inspect. That value is the threshold a new candidate must beat.

A min-heap provides exactly this operation. Every parent is no greater than its children, so the root is the minimum of the retained values. Unlike a binary search tree, a heap does not order the rest of the values globally; you cannot use it to search efficiently for an arbitrary value.

Watch the contrast between keeping all values in a max-heap and keeping only the current top $k$ in a min-heap.

Here is the invariant to carry into the implementation: after processing any prefix of the stream, the heap contains the largest $\min (k,\text{items seen})$ values from that prefix, counting duplicates. The contents need not be sorted.

Once the heap is full, a new value no greater than its root cannot enter the top $k$; discard it. A larger value replaces the root, and the heap restores its ordering. For example, with $k=3$, after seeing 5, -2, 8, the retained values are -2, 5, 8. The next value, 8, replaces -2, leaving 5, 8, 8. Both occurrences of 8 count.

How the array maintains the invariant

A binary heap has two properties. It is a complete binary tree—each level fills from left to right—and it obeys its min- or max-order rule. Completeness lets an array represent its shape without child pointers.

The image below shows a max-heap. Use it to see the two repair movements, but reverse its comparisons for our min-heap: a newly inserted smaller value can swim up, while an excessively large root must sink down.

The following C implementation uses one-based indices. Read it for the repair logic rather than copying its interface: our fixed-capacity top-$k$ implementation will use zero-based indices and need not allocate space for more than $k$ values.

With zero-based indices, a node at index $i$ has parent $(i-1)/2$ when $i>0$, and children $2i+1$ and $2i+2$ when those indices exist. An insertion appends at the end and swims toward a parent. Replacing the root keeps the heap size fixed and sinks the new root toward its smaller child. Each movement crosses at most the heap’s height, so it takes $O(\log k)$ time.

Implement bounded top-$k$ selection in C

The program below owns one array of capacity $k$. Its add operation must handle three cases: the heap is not full, the new value does not beat the root, or it does beat the root. Complete the two TODO functions, then run the tests. Budget about 18 minutes for implementation and 5 minutes to inspect any failing case.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *a;          /* zero-based min-heap */
    size_t size;
    size_t capacity;
} TopK;

static bool topk_init(TopK *h, size_t k)
{
    h->a = NULL;
    h->size = 0;
    h->capacity = 0;

    if (k == 0)
        return true;
    if (k > SIZE_MAX / sizeof(*h->a))
        return false;

    h->a = malloc(k * sizeof(*h->a));
    if (h->a == NULL)
        return false;

    h->capacity = k;
    return true;
}

static void swap_int(int *x, int *y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

static void swim(TopK *h, size_t i)
{
    while (i > 0) {
        size_t parent = (i - 1) / 2;
        if (h->a[parent] <= h->a[i])
            break;
        swap_int(&h->a[parent], &h->a[i]);
        i = parent;
    }
}

/* Restore min-heap order after the root becomes too large. */
static void sink(TopK *h, size_t i)
{
    /* TODO: compare with the smaller existing child; swap if needed. */
}

/* Retain the largest capacity values seen so far, including duplicates. */
static void topk_add(TopK *h, int value)
{
    /* TODO: handle capacity zero, a partially filled heap,
       and a full heap. Never exceed the allocated capacity. */
}

static size_t count_value(const TopK *h, int value)
{
    size_t count = 0;
    for (size_t i = 0; i < h->size; ++i)
        if (h->a[i] == value)
            ++count;
    return count;
}

int main(void)
{
    TopK h;
    assert(topk_init(&h, 3));

    const int input[] = {5, -2, 8, 8, 1, 10, 4};
    const size_t n = sizeof(input) / sizeof(input[0]);

    for (size_t i = 0; i < n; ++i) {
        topk_add(&h, input[i]);
        if (i == 3) {            /* 5, -2, 8, 8 processed */
            assert(h.size == 3);
            assert(h.a[0] == 5);
        }
    }

    assert(h.size == 3);
    assert(h.a[0] == 8);
    assert(count_value(&h, 8) == 2);
    assert(count_value(&h, 10) == 1);
    free(h.a);

    assert(topk_init(&h, 0));
    topk_add(&h, 42);
    assert(h.size == 0);
    free(h.a);

    assert(topk_init(&h, 4));
    topk_add(&h, -5);
    topk_add(&h, -1);
    assert(h.size == 2);         /* fewer than k items seen */
    assert(h.a[0] == -5);
    free(h.a);

    puts("Top-k tests passed");
    return 0;
}

Save it as topk.c and compile with warnings and sanitizers:

gcc -std=c11 -O0 -g -Wall -Wextra -Wpedantic \
    -fsanitize=address,undefined topk.c -o topk
./topk

The tests inspect the root and the multiset of retained values, not array order. For sink, take care when only the left child exists. The loop condition in the solution below ensures that computing the left-child index is safe for this heap size.

Check the replacement and explain why it works

Compare your TODO replacements with this implementation:

static void sink(TopK *h, size_t i)
{
    while (i < h->size / 2) {
        size_t child = 2 * i + 1; /* left child exists */
        size_t right = child + 1;

        if (right < h->size && h->a[right] < h->a[child])
            child = right;

        if (h->a[i] <= h->a[child])
            break;

        swap_int(&h->a[i], &h->a[child]);
        i = child;
    }
}

static void topk_add(TopK *h, int value)
{
    if (h->capacity == 0)
        return;

    if (h->size < h->capacity) {
        size_t i = h->size++;
        h->a[i] = value;
        swim(h, i);
        return;
    }

    if (value <= h->a[0])
        return;

    h->a[0] = value;
    sink(h, 0);
}

Why is replacing the root sufficient? Once the heap is full, its root is the smallest of the current top $k$. A value larger than that root belongs among the top $k$, and the old root is the one retained value it displaces. Only the new root might violate min-heap order, so sink repairs it. If the new value equals the root, discarding it still leaves a valid top-$k$ multiset of values; the particular occurrence retained is unspecified.

For $n$ incoming values and $k>0$, each value requires at most $O(\log k)$ heap work. The total time is $O(n\log (k+1))$, and the heap uses $O(k)$ additional space. When $k=1$, this is simply a running maximum. If $k>n$, the heap holds all $n$ seen values; its root is the smallest seen, not a defined “$k$-th largest” value. Once at least $k$ values have arrived, the root is the current $k$-th largest value, counting duplicates. Producing the retained values in sorted order would require additional work; heap order alone does not provide sorted output.

Key takeaways

For streaming top-$k$, orient the heap so its root is the least desirable retained candidate: a min-heap for the largest $k$ values. State the prefix invariant, keep storage bounded at $k$, and repair heap order only where insertion or root replacement can break it. In an interview, clarify whether duplicates count and whether the caller wants an unordered set of candidates, a $k$-th value, or sorted output.

Next, you’ll combine two structures: a hash table for direct lookup and a doubly linked list for recency order in an LRU cache.