Fixed-Size Min-Heap Based Top-K Selection

If you only need the 100 slowest requests out of tens of millions, sorting the entire dataset does far more work than the requirement calls for.

What you actually need is to retain only the candidates that could belong to the top K. A min-heap of size K works well for this: keep the weakest element among the current top K at the root, and for each new item, simply check whether it is stronger than that root.

Because heap insertion and removal each cost O(log K) relative to the heap size, a single pass over all N inputs costs O(N log K) in total, and memory usage is O(K). The C++ standard draft notes that adding and removing heap elements can be done in O(log N) time, and the Complexity clauses for individual push_heap and pop_heap operations bound the number of comparisons at log N and 2 log N, respectively. ¹

O(N log K) is an upper bound, and it is worth keeping that in mind. Once the heap is full with K elements, most candidates are eliminated by a single comparison against the root and never touch the heap.
When the first K elements are inserted one by one into the heap, as in the implementation shown below, the expected cost for random input can be expressed as roughly O(K + N + K(H_N - H_K) log K).

Here, H_n denotes the harmonic number.

It is worth noting why the first term is K rather than K log K. When pushing a random permutation into a heap one element at a time, the average sift-up distance is O(1), making the entire build linear. Hayward and McDiarmid's analysis gives the average number of comparisons for Williams's repeated insertion as approximately 2.28K. The worst case is still K log K, but in terms of expected cost, the build can be described as linear.

For the workload in this post where K << N, the overall cost simplifies to O(N + K log K log(N/K)). For example, with N equal to 50 million and K equal to 100, the expected number of heap updates is about 1,312, and the vast majority of remaining inputs are eliminated by a single comparison against the root.

Measured: 931   times Formula: 921 times
Measured: 1,077 times Formula: 1,081 times

(from my own measurements)
Conversely, if the input is already sorted in ascending order, every element triggers an update and the upper bound is reached. This distinction matters when interpreting benchmark results.

A common point of confusion is that the root of a min-heap is not the "best" value but the first candidate to be evicted from the current top K. When searching for the slowest requests, the request with the smallest latency within the top K sits at the root. If a new request is slower than the root, the root is removed and the new request is inserted; if it is faster, it is discarded. The heap size never exceeds K.

A personal note: the most common source of confusion for beginners is the directionality of min-heap versus max-heap. The reason you use a min-heap to find the K largest elements is the cutoff (the boundary, or threshold).

However, if you put only latency in the comparator, production results can be non-deterministic. When multiple requests share the same latency, which ones remain in the top K depends on the stability guarantees of the container.

The Python heapq documentation also notes that heap sort is not stable and that a separate tie-breaker may be needed for equal-priority items. The .NET PriorityQueue similarly states that FIFO ordering is not guaranteed for elements with equal priority.

Accordingly, this example defines (latencyMicros DESC, requestId ASC) as a complete ranking contract. ([Python documentation]²)

This contract has one prerequisite: requestId must be unique for a total order to hold. If IDs are duplicated, the comparator returns false in both directions, making the two elements equivalent and leaving it up to the implementation which one survives. In systems that use at-least-once delivery, retries, or client-generated IDs, you need to add a third key such as a receive sequence number.

This pattern is particularly well-suited to cases like streaming telemetry, log analysis, leaderboard candidate extraction, and anomaly ranking, where K << N and there is no need to store the entire input. On the other hand, when K approaches N, the overhead of maintaining the heap may outweigh any advantage. The official Python documentation also notes that nlargest/nsmallest are efficient for small n, while a full sort may be more appropriate for large n.

A top-K heap is the right tool when the ratio of input size to K justifies the choice (²)

In production, what you store in the heap also matters. If you're searching for the 100 slowest requests and you stuff the request body, response body, and tracing tree into the heap, a massive object graph can stay pinned in memory even when K is small. It is safer to keep only the immutable key needed for ranking and the minimal summary needed for final output in the heap.

Quick Summary

Ranking:
A is better than B
=
A.latencyMicros > B.latencyMicros
or latencies are equal and
A.requestId < B.requestId

Heap:
Only stores the current Top-K
root
=
The worst element among the current Top-K

New candidate:
heap.size < K
→ insert
candidate > root
→ remove root
→ insert candidate
candidate <= root
→ discard

Complexity:
Scan:
O(N log K)
Memory:
O(K)
Final sort:
O(K log K)

1. Problem Setup

Suppose an API gateway observes the latency of 50 million requests over the course of a day.

The only information needed from each request is as follows.

LatencySample
- requestId
- latencyMicros

Goal:

Top 100 Slowest Requests

Input:

requestId  latencyMicros
101        1,250
102           82
103        8,400
104          910
105        8,400
...

Ranking contract:

Primary:
higher latencyMicros takes priority
Secondary:
if latency is equal,
lower requestId takes priority

Therefore:

103 / 8400
105 / 8400
101 / 1250
104 / 910
102 / 82

in that order.

When K = 3, the values to maintain are:

103 / 8400
105 / 8400
101 / 1250

However, inside the heap, the following element is the root.

101 / 1250

This is because 101 is the element that must be evicted first from the current Top-3.

New request:

106 / 500

is weaker than the root.

500 < 1250
-> discard immediately

Conversely:

107 / 2200

then:

2200 > 1250
-> remove 101
-> insert 107

it becomes.

Personal note: I use this when checking total cost in defense workload testing after a DDoS test. Because it streams the risk scores of attack candidates and keeps only the top K in a min-heap, most candidates are eliminated with a single comparison against the heap root once a cutoff is established. I've found it genuinely useful in practice.

2. Core Expressions

C++23

In C++, small value objects are placed into a generic bounded heap. A single Comparator defines both the final sort order and the heap cutoff semantics simultaneously.

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <queue>
#include <ranges>
#include <utility>
#include <vector>

class LatencySample final
{
public:
    constexpr LatencySample(
        std::uint64_t requestId,
        std::uint32_t latencyMicros) noexcept
        : requestId_(requestId),
          latencyMicros_(latencyMicros)
    {
    }

    [[nodiscard]]
    constexpr std::uint64_t getRequestId() const noexcept
    {
        return requestId_;
    }

    [[nodiscard]]
    constexpr std::uint32_t getLatencyMicros() const noexcept
    {
        return latencyMicros_;
    }

private:
    std::uint64_t requestId_;
    std::uint32_t latencyMicros_;
};

struct BetterLatencyRank final
{
    [[nodiscard]]
    constexpr bool operator()(
        const LatencySample& left,
        const LatencySample& right) const noexcept
    {
        if (left.getLatencyMicros()
            != right.getLatencyMicros())
        {
            return left.getLatencyMicros()
                > right.getLatencyMicros();
        }

        return left.getRequestId()
            < right.getRequestId();
    }
};

template<
    std::copy_constructible T,
    typename Better>
requires std::strict_weak_order<
    Better,
    const T&,
    const T&>
class BoundedTopK final
{
public:
    BoundedTopK(
        std::size_t limit,
        Better better)
        : limit_(limit),
          better_(std::move(better)),
          heap_(better_)
    {
    }

    void add(T candidate)
    {
        if (limit_ == 0)
        {
            return;
        }

        if (heap_.size() < limit_)
        {
            heap_.push(std::move(candidate));
            return;
        }

        replaceWorstIfBetter(
            std::move(candidate));
    }

    [[nodiscard]]
    std::vector<T> finish() &&
    {
        std::vector<T> result;
        result.reserve(heap_.size());

        while (!heap_.empty())
        {
            result.push_back(
                heap_.top());
            heap_.pop();
        }

        std::ranges::sort(
            result,
            better_);

        return result;
    }

private:
    std::size_t limit_;
    Better better_;
    std::priority_queue<
        T,
        std::vector<T>,
        Better> heap_;

    void replaceWorstIfBetter(
        T candidate)
    {
        if (!better_(
            candidate,
            heap_.top()))
        {
            return;
        }

        heap_.pop();
        heap_.push(
            std::move(candidate));
    }
};

Usage:

BoundedTopK<
    LatencySample,
    BetterLatencyRank> topK{
        100,
        BetterLatencyRank{}};

for (const LatencySample& sample : samples)
{
    topK.add(sample);
}

std::vector<LatencySample> slowest =
    std::move(topK).finish();

finish() && prevents calls on lvalues but does not consume the object like a linear type. Code that calls std::move(topK).finish() again will still compile.

The first call empties the heap, so the second call simply returns an empty vector.

It is also worth noting that finish() copies elements. Because std::priority_queue::top() returns const T&, no move occurs in result.push_back(heap_.top()).

For the compact value structs this post assumes, K copies are negligible; however, if you stored heavy objects in the heap as warned in Section 5, you pay that cost again here. The workaround of const_cast-ing away top() to move from it is not guaranteed by the standard and should be avoided. If needed, it is better to use std::vector directly as the underlying container and call std::pop_heap / pop_back manually.

The comparator direction in std::priority_queue can feel backwards at first glance. Here, BetterLatencyRank expresses an ordering where "better elements come first," and when that ordering is passed to the priority queue, top() holds the element that is last in that ordering, namely the worst retained value.

The complexity justification comes through one additional step. The standard's [priority.queue] clause has no separate Complexity provision for push or pop. Instead, it specifies push as "as if by: c.push_back(x); push_heap(c.begin(), c.end(), comp)" and pop as "as if by: pop_heap(c.begin(), c.end(), comp); c.pop_back()".

Therefore, $O(\log K)$ is not a guarantee made by priority_queue itself but is inherited from the comparison-count upper bound in [alg.heap.operations] via this as-if specification.

That clause bounds push_heap to no more than $\log(\text{last} - \text{first})$ comparisons and pop_heap to no more than $2\log(\text{last} - \text{first})$ comparisons. Actual total runtime is also affected by the cost of the comparator and the underlying container. (³, ¹)

Python

Python's heapq is a min-heap by default, with heap[0] holding the smallest element. heapreplace() removes the minimum element and inserts a new value, and the official documentation describes it as the operation suited for a fixed-size heap. ([Python documentation]²)

from __future__ import annotations

from dataclasses import dataclass, field
from heapq import heapreplace, heappush


@dataclass(frozen=True, slots=True)
class LatencySample:
    request_id: int
    latency_micros: int


@dataclass(order=True, slots=True, frozen=True)
class _HeapItem:
    latency_micros: int
    inverted_request_id: int
    sample: LatencySample = field(
        compare=False
    )


class BoundedTopKLatency:
    def __init__(
        self,
        limit: int,
    ) -> None:
        if limit < 0:
            raise ValueError(
                "`limit` must be greater than or equal to 0."
            )

        self._limit = limit
        self._heap: list[_HeapItem] = []

    def add(
        self,
        sample: LatencySample,
    ) -> None:
        if self._limit == 0:
            return

        if len(self._heap) < self._limit:
            heappush(
                self._heap,
                _to_heap_item(sample),
            )
            return

        self._replace_if_better(
            sample
        )

    def finish(
        self,
    ) -> tuple[LatencySample, ...]:
        result = [
            item.sample
            for item in self._heap
        ]
        result.sort(
            key=lambda sample: (
                -sample.latency_micros,
                sample.request_id,
            )
        )
        return tuple(result)

    def _replace_if_better(
        self,
        sample: LatencySample,
    ) -> None:
        root = self._heap[0]
        root_request_id = -root.inverted_request_id

        if (
            sample.latency_micros < root.latency_micros
            or (
                sample.latency_micros
                == root.latency_micros
                and sample.request_id >= root_request_id
            )
        ):
            return

        heapreplace(
            self._heap,
            _to_heap_item(sample),
        )


def _to_heap_item(
    sample: LatencySample,
) -> _HeapItem:
    return _HeapItem(
        latency_micros=(
            sample.latency_micros
        ),
        inverted_request_id=(
            -sample.request_id
        ),
        sample=sample,
    )

Usage:

top_k = BoundedTopKLatency(
    limit=100
)

for sample in samples:
    top_k.add(sample)

slowest = top_k.finish()

inverted_request_id is needed to make the min-heap root the "worst retained record."

Setting _HeapItem to frozen=True is intentional. As discussed in Section 5, mutating a ranking field after an item has been inserted into the heap breaks the guarantee that the root is the minimum. If only the LatencySample outside the heap is immutable while the item actually stored in the heap remains mutable, that rule is not enforced by the code. Since heapq swaps list slots without modifying the items themselves, using frozen has no effect on behavior.

While the heap is not yet full, a _HeapItem is created and stored. Once the heap is full, the two fields of the LatencySample are compared against the root first, and a _HeapItem is created only when the candidate is actually worth replacing. This way, no temporary object is created for every rejected input. The number of retained elements remains O(K), and after the heap is full, the number of _HeapItem creations is proportional to the number of replacements.

When latency values are equal:

Smaller requestId
→ better
Larger requestId
→ worse
→ should go toward the heap root

In summary:

heap key:
(
    latency,
    -requestId
)

is used.

C#

.NET's PriorityQueue<TElement,TPriority> is a min-priority queue that dequeues the element with the lowest priority first, and the current implementation is an array-based quaternary min-heap. It also does not guarantee FIFO ordering for elements with equal priority. For this reason, the code includes requestId inside the priority as well. ([Microsoft Learn]⁴)

using System;
using System.Collections.Generic;

public readonly struct LatencySample
{
    private readonly ulong requestId;
    private readonly uint latencyMicros;

    public LatencySample(
        ulong requestId,
        uint latencyMicros)
    {
        this.requestId = requestId;
        this.latencyMicros = latencyMicros;
    }

    public ulong GetRequestId()
    {
        return this.requestId;
    }

    public uint GetLatencyMicros()
    {
        return this.latencyMicros;
    }
}

internal readonly struct RankKey
    : IComparable<RankKey>
{
    private readonly uint latencyMicros;
    private readonly ulong requestId;

    private RankKey(
        uint latencyMicros,
        ulong requestId)
    {
        this.latencyMicros = latencyMicros;
        this.requestId = requestId;
    }

    public static RankKey From(
        in LatencySample sample)
    {
        return new RankKey(
            sample.GetLatencyMicros(),
            sample.GetRequestId());
    }

    public int CompareTo(
        RankKey other)
    {
        int latencyOrder =
            this.latencyMicros.CompareTo(
                other.latencyMicros);

        if (latencyOrder != 0)
        {
            return latencyOrder;
        }

        return other.requestId.CompareTo(
            this.requestId);
    }
}

public sealed class BoundedTopKLatency
{
    private readonly int limit;
    private readonly PriorityQueue<
        LatencySample,
        RankKey> heap;

    public BoundedTopKLatency(
        int limit)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(
            limit);

        this.limit = limit;
        this.heap =
            new PriorityQueue<
                LatencySample,
                RankKey>(
                Math.Max(1, limit));
    }

    public void Add(
        in LatencySample sample)
    {
        if (this.limit == 0)
        {
            return;
        }

        RankKey rank =
            RankKey.From(
                in sample);

        if (this.heap.Count < this.limit)
        {
            this.heap.Enqueue(
                sample,
                rank);
            return;
        }

        this.heap.EnqueueDequeue(
            sample,
            rank);
    }

    public LatencySample[] Finish()
    {
        LatencySample[] result =
            new LatencySample[
                this.heap.Count];

        for (
            int index = result.Length - 1;
            index >= 0;
            index -= 1)
        {
            result[index] =
                this.heap.Dequeue();
        }

        return result;
    }
}

Usage:

BoundedTopKLatency topK =
    new(limit: 100);

foreach (LatencySample sample in samples)
{
    topK.Add(in sample);
}

LatencySample[] slowest =
    topK.Finish();

EnqueueDequeue() is a combined operation that inserts a new element and immediately removes the minimum element; Microsoft documents it as generally more efficient than separate enqueue and dequeue heap operations. If the candidate is worse than the current Top-K, the candidate itself becomes the minimum element and is removed; if the candidate is better, the existing cutoff is removed. ([Microsoft Learn]⁵)

TypeScript

In TypeScript, the ranking contract is defined as a separate function, and a small binary min-heap is used.

Comparator rules:

< 0
-> left is worse
> 0
-> left is better

export type LatencySample =
  Readonly<{
    requestId: bigint;
    latencyMicros: number;
  }>;

type Comparator<T> =
  (
    left: T,
    right: T,
  ) => number;

class MinHeap<T>
{
  readonly #values: T[] = [];
  readonly #compare: Comparator<T>;

  public constructor(
    compare: Comparator<T>,
  )
  {
    this.#compare = compare;
  }

  public getSize(): number
  {
    return this.#values.length;
  }

  public peek(): T | undefined
  {
    return this.#values[0];
  }

  public push(
    value: T,
  ): void
  {
    this.#values.push(value);
    this.#siftUp(
      this.#values.length - 1,
    );
  }

  public replaceRoot(
    value: T,
  ): T
  {
    const previous =
      this.#values[0];
    this.#values[0] = value;
    this.#siftDown(0);
    return previous;
  }

  public copyValues(): T[]
  {
    return [...this.#values];
  }

  #siftUp(
    startIndex: number,
  ): void
  {
    let index = startIndex;

    while (index > 0) {
      const parent =
        Math.floor(
          (index - 1) / 2,
        );

      if (!this.#isLess(
        index,
        parent,
      )) {
        return;
      }

      this.#swap(
        index,
        parent,
      );
      index = parent;
    }
  }

  #siftDown(
    startIndex: number,
  ): void
  {
    let index = startIndex;

    while (true) {
      const child =
        this.#findSmallerChild(
          index,
        );

      if (child === undefined
        || !this.#isLess(
          child,
          index,
        )) {
        return;
      }

      this.#swap(
        index,
        child,
      );
      index = child;
    }
  }

  #findSmallerChild(
    parent: number,
  ): number | undefined
  {
    const left =
      parent * 2 + 1;

    if (left >= this.#values.length) {
      return undefined;
    }

    const right = left + 1;

    if (right >= this.#values.length) {
      return left;
    }

    return this.#isLess(
      right,
      left,
    )
      ? right
      : left;
  }

  #isLess(
    left: number,
    right: number,
  ): boolean
  {
    return this.#compare(
      this.#values[left],
      this.#values[right],
    ) < 0;
  }

  #swap(
    left: number,
    right: number,
  ): void
  {
    [
      this.#values[left],
      this.#values[right],
    ] = [
      this.#values[right],
      this.#values[left],
    ];
  }
}

export class BoundedTopKLatency
{
  readonly #limit: number;
  readonly #heap =
    new MinHeap<LatencySample>(
      compareLatencyRank,
    );

  public constructor(
    limit: number,
  )
  {
    if (!Number.isSafeInteger(limit)
      || limit < 0) {
      throw new RangeError(
        "`limit` must be a safe integer greater than or equal to 0.",
      );
    }

    this.#limit = limit;
  }

  public add(
    sample: LatencySample,
  ): void
  {
    if (this.#limit === 0) {
      return;
    }

    if (this.#heap.getSize()
      < this.#limit) {
      this.#heap.push(sample);
      return;
    }

    this.#replaceIfBetter(
      sample,
    );
  }

  public finish():
    readonly LatencySample[]
  {
    const result =
      this.#heap.copyValues();

    result.sort(
      (left, right) =>
        -compareLatencyRank(
          left,
          right,
        ),
    );

    return result;
  }

  #replaceIfBetter(
    sample: LatencySample,
  ): void
  {
    const worst =
      this.#heap.peek();

    if (worst === undefined
      || compareLatencyRank(
        sample,
        worst,
      ) <= 0) {
      return;
    }

    this.#heap.replaceRoot(
      sample,
    );
  }
}

export function compareLatencyRank(
  left: LatencySample,
  right: LatencySample,
): number
{
  if (
    left.latencyMicros
    !== right.latencyMicros
  ) {
    return (
      left.latencyMicros
      - right.latencyMicros
    );
  }

  if (left.requestId
    < right.requestId) {
    return 1;
  }

  if (left.requestId
    > right.requestId) {
    return -1;
  }

  return 0;
}

Usage:

const topK =
  new BoundedTopKLatency(
    100,
  );

for (const sample of samples) {
  topK.add(sample);
}

const slowest =
  topK.finish();

3. Call site

In real systems, you do not put the entire network DTO into the heap.

Network Event
-> Validation
-> Compact Ranking Record
-> Top-K Heap

For example, suppose a transport event is much larger, as shown below.

export type LatencyEvent =
  Readonly<{
    requestId: bigint;
    durationNanos: bigint;
    requestBody?: Uint8Array;
    responseBody?: Uint8Array;
    headers:
      Readonly<Record<string, string>>;
  }>;

Only two values are needed for Top-K selection.

export type LatencySource =
  Readonly<{
    readChunkAsync: (
      signal?: AbortSignal,
    ) => Promise<
      readonly LatencyEvent[]
      | undefined
    >;
  }>;

export async function collectSlowestAsync(
  source: LatencySource,
  limit: number,
  signal?: AbortSignal,
): Promise<
  readonly LatencySample[]
>
{
  const topK =
    new BoundedTopKLatency(
      limit,
    );

  while (true) {
    const chunk =
      await source.readChunkAsync(
        signal,
      );

    if (chunk === undefined) {
      return topK.finish();
    }

    addChunk(
      topK,
      chunk,
    );
  }
}

function addChunk(
  topK: BoundedTopKLatency,
  events: readonly LatencyEvent[],
): void
{
  for (const event of events) {
    const sample =
      normalizeLatency(event);
    topK.add(sample);
  }
}

function normalizeLatency(
  event: LatencyEvent,
): LatencySample
{
  if (event.durationNanos < 0n) {
    throw new RangeError(
      "`durationNanos` cannot be negative.",
    );
  }

  const micros =
    event.durationNanos / 1_000n;

  if (micros > 0xffff_ffffn) {
    throw new RangeError(
      "`latencyMicros` is out of range.",
    );
  }

  return {
    requestId:
      event.requestId,
    latencyMicros:
      Number(micros),
  };
}

One thing to watch out for with unit conversion is that durationNanos / 1_000n is BigInt integer division and truncates. 1999ns and 1000ns both become the same 1μs.

Reducing nanosecond-resolution observations to microseconds means that different requests can fall into the same rank bucket, which gives the tie-breaker requestId a more significant role as the effective sort key. In particular, within a microsecond bucket that matches the cutoff, requestId determines which element survives. If resolution matters, keep the value in nanoseconds and raise the upper-bound check to uint64.

Responsibilities are separated as follows.

LatencySource
= network/file I/O
= cancellation
= chunk lifetime

Boundary Validation
= ID validity
= blocks negative durations
= unit conversion
= integer range validation

LatencySample
= only owns the minimum value needed for Top-K

BoundedTopK
= ranking
= maintains cutoff
= O(K) memory

Caller
= orchestrates I/O and ranking

Reporting Layer
= allows detailed trace retrieval
only for the final K items

In particular, the following pattern should be avoided.

Top-K heap
-> requestBody 5 MiB
-> responseBody 20 MiB
-> header map
-> tracing graph

Even with K set to 100, this can hold on to object graphs of several GiB.

A better structure would look like the following.

Heap:
requestId
latencyMicros

After final Top-K is determined:
requestId
-> query detailed trace if needed

4. Reading order

1.
What exactly does the ranking of "better value" mean?
↓ 
2.
Is there a total order that covers tie-breaking as well?
↓ 
3.
Is the heap root the worst element
in the current Top-K?
↓ 
4.
Does the heap size never exceed K?
↓ 
5.
Is a replacement made only when a candidate
is better than the root?
↓ 
6.
Is the internal heap array
not being mistaken for a sorted result?
↓ 
7.
Is the final sort performed only on the K elements?
↓ 
8.
Is the heap holding on to
heavy original objects unnecessarily?
↓ 
9.
Are the values used for ranking
immutable after insertion?
↓ 
10.
Does the ratio of K to N
actually justify using heap selection?

The question of when to use it is as follows (and this is, in essence, the core of the algorithm).

5. Boundaries and Misconceptions

A heap is not a sorted collection

What a min-heap guarantees is the heap invariant: the root is the minimum element. The Python official documentation explicitly states that heap[0] is the smallest element. There is no guarantee that the entire internal array of the heap is sorted. ([Python documentation]²)

Therefore:

Heap internal iteration
→ output final ranking

it should not be used this way.

If the final output requires ordering as well:

Full sort of N elements

rather than:

Final sort of only K elements

you should do this.

The comparator direction is the most common mistake

Goal:

Top K Largest

but if you use a max-heap, the root becomes the best value.

Then, when a new candidate arrives, you cannot immediately tell which element should be discarded.

For Top-K largest:

min-heap

this is the natural approach.

Conversely, for Bottom-K smallest, a max-heap is the natural approach.

Do not delegate tie-breaking to container stability

The current ranking:

latency DESC
requestId ASC

is intentional.

The Python documentation notes that heap-based sort is not stable, and also describes a technique of inserting a separate entry count as a tie-breaker when handling items of equal priority. .NET PriorityQueue likewise does not guarantee FIFO ordering for equal priorities. ([Python documentation]²)

A production comparator should include, as much as possible:

primary score
secondary immutable ID

as well.

Do not pass NaN directly as a floating-point score

In the following comparator:

left.score > right.score

if score = NaN, the ordering relation may not satisfy a valid strict weak ordering.

This example normalizes latency to:

uint32 microseconds

before ranking.

If your model requires a real-valued score, you must enforce:

finite
not NaN

at the ingestion boundary.

Personal note: I am currently using code blocks for important emphasis, but I am not sure whether that is the right choice for visibility. On the other hand, it is also difficult to use a different approach for this kind of emphasis. These days, widgets styled after macOS UI patterns are popular, and I am debating whether to incorporate them as well. However, the current UI mockup does not feel quite right, so I am uncertain how to best handle readability for my readers.

Do not modify the ranking field of an element after it has been inserted into the heap

The following scenarios can lead to incorrect behavior.

heap.add(sample)
Afterwards:
sample.latency = ...

The heap builds its tree invariant based on the comparator result at the time of insertion.

If an element's priority is changed externally, there is no longer any guarantee that the root is actually the minimum value.

Heap elements should be:

immutable value

immutable, or the heap itself must manage update operations.

This structure is especially well-suited for append-only observations

The following workloads:

Keep adding new samples
-> Top-K at the end

are an excellent fit.

On the other hand:

Updating the score of an existing item
Deleting an existing item
Refreshing the priority of an arbitrary item

if these occur frequently, a simple bounded heap is not appropriate.

In that case, consider:

indexed heap
balanced tree
ordered set
Recalculation

among other alternatives.

When K is close to N, a heap is not the obvious answer

For example:

N = 1,000,000
K = 900,000

you end up inserting nearly every value into the heap and still paying the log K maintenance cost.

The Python documentation also explicitly states that nlargest/nsmallest performs best for small n, and that sorted() may be more efficient for large n. ([Python documentation]²)

In practice:

K << N
→ prioritize bounded heap
K ≈ N
→ benchmark sort / partition selection

is the right call.

If K = 1, you don't even need a heap

If you only need the single slowest request:

running max

is sufficient.

O(N)
memory O(1)

is the answer.

The Python documentation likewise notes that when n == 1, direct operations like min()/max() are more appropriate. ([Python documentation]²)

K cannot be increased after the fact

If you process the stream from the start

K = 100

with a fixed K, all data ranked 101st and below has already been discarded.

Later,

Let's change K to 1000

even if you want more, there is no way to recover that data.

The necessary choice:

source replay
Maintaining from the start with a larger K
Preserving the raw archive

of the common pitfalls.

Bounded selection is an algorithm that intentionally discards information.

A heap does not perform deduplication.

If the same event arrives twice:

request 42
request 42

both entries can end up in the Top-K.

Top-K and deduplication are separate concerns.

Top-K
= ranking selection

Dedup
= identity uniqueness

Do not mix the two inside the heap code.

Placing heavy objects into the heap changes the meaning of K.

Memory complexity is commonly written as:

O(K)

but the actual byte cost is:

O(
  K × retainedObjectGraphSize
)

in practice.

In C++, storing a shared_ptr<Request> in the heap can keep the request body and the downstream object graph alive indefinitely.

In Python, C#, and TypeScript as well, storing an object reference in the heap can prevent that entire object graph from being garbage collected.

For this reason, Top-K should store, wherever possible:

compact immutable summary

lightweight value types (e.g., a score and an ID).

In managed languages, there is an additional allocation pressure on top of this. If you create a new wrapper object for the heap for every one of tens of millions of stream elements, the GC keeps scanning that garbage even if most objects are discarded immediately. That is why the Python implementation in this post first compares the root against raw fields before the heap is full, and only constructs a _HeapItem when a replacement is confirmed; the C# implementation uses a readonly struct rather than a class for the same reason.

If the ranking key is small enough, you can eliminate the wrapper entirely. If latencyMicros fits in a uint32 and requestId fits in a uint32, then:

packed = (uint64(latencyMicros) << 32) | uint32(requestId)

you can pack them into a single integer and push only that onto the heap. However, this trick does not work as-is when the tie-break direction is ascending by ID. Because the contract in this post is latency DESC + requestId ASC, the lower 32 bits must hold ~requestId rather than requestId so that the min-heap root remains the worst element under the contract. Use bit-packing only when the width and sort direction of every field are fixed, and if that assumption is not documented, adding even one field later will break things silently.

Do not parallelize by locking a shared heap

If multiple workers lock the same heap for each sample:

Worker A ─┐
Worker B ─┼-> lock -> global heap
Worker C ─┘

lock contention can become a larger cost than the ranking itself.

Top-K has a nicer property.

Local Top-K from each partition
-> Then Top-K again from the union of Local Top-Ks
-> Global Top-K

produces exact results.

In parallel/distributed environments:

local heap
-> merge

is the natural approach.

Local Top-K merging is not an approximation

There is, however, a prerequisite. Each partition must retain up to the global K elements; if the number of elements in a partition is smaller than the global K, simply retain all elements in that partition. Reducing the local K below the global K will produce incorrect results. Setting it higher than the global K does not break correctness, but it does increase the number of candidates sent to the coordinator.

Suppose an element x in partition P did not make it into the local Top-K.

Then within P there are already:

At least K elements better than x

that exist.

Those K elements exist as-is in the global input as well.

Therefore, x cannot enter the global Top-K either.

That is:

TopK(
  Full input
)
=
TopK(
  The union of each partition's Top-K results
)

holds.

This property is extremely useful for distributed aggregation.

Without a complete ranking, distributed merge results become unstable

If you compare only latency with no tie-breaking:

Partition A
Partition B

which candidate with the same score survives can vary depending on the heap implementation or arrival order.

The more distributed the Top-K scenario is:

(score, uniqueId)

a total rank of this form becomes even more important.

When does it fail?

Using a max-heap for Top-K largest selection
Assuming the heap root is the largest element
Assuming the heap array itself is sorted
Not defining tie-breaking behavior for equal latency values
Delegating tie handling to container stability
Using a float comparator as-is when NaN values are present
Mutating ranking fields after insertion
Storing the entire request body in the heap when K=100
Always using a heap even when K is close to N
Creating a priority queue when K=1
Assuming K can be increased later
Assuming the Top-K heap also performs deduplication
Multiple workers acquiring a global heap lock on every sample

6. Bad Example

Let's look at the simplest possible TypeScript implementation.

export function slowestRequestsBad(
  samples: LatencySample[],
  limit: number,
): LatencySample[]
{
  samples.sort(
    (left, right) =>
      right.latencyMicros
      - left.latencyMicros,
  );

  return samples.slice(
    0,
    limit,
  );
}

This code is not always bad code.

If the input is only a few hundred items, this approach can actually be simpler and fast enough.

The problem is:

N = 50,000,000
K = 100

applying it as-is to the same requirements.

First problem:

Sorting all N elements
O(N log N)

it does.

What is actually needed is:

Maintaining 100 candidates

that alone.

The second problem is that it directly mutates the input array.

samples.sort(...)

As a result, the original input order that the caller expected is lost.

The third problem is the absence of a tie-breaker.

request 10 / 8400
request 20 / 8400

The domain contract does not define which of these comes first.

The fourth problem is that it requires the entire input to already be in memory.

Streaming source:

network
file
generator
database cursor

if only the Top-K elements are needed from it, full materialization is unnecessary.

The right choice depends on the workload.

Small N
→ sort is simpler

K ≈ N
→ consider sort/partition

Large N
AND
Small K
AND
Streaming
→ bounded Top-K heap

Third option: partition selection

Let's now unpack partition selection, which came up twice earlier. It is a selection algorithm that partitions an array to find only the K-th boundary, discarding the side that doesn't need further processing. In C++, std::nth_element provides this operation, though the standard does not mandate a specific implementation algorithm such as introselect. The average comparison complexity for the non-parallel overload is linear, but the standard does not fix the general worst-case complexity.

full sort
O(N log N)

bounded heap
O(N log K) upper bound
Expected O(N + K log K log(N/K))

nth_element
Average O(N) / average linear
Typical worst-case complexity is not specified by the standard

The selection criteria are as follows.

There are trade-offs. nth_element rearranges the input array, which means it carries the same mutation problem noted at the start of Section 6. The result is also not sorted, so the K elements must be sorted separately afterward. Nor is it stable. Even so, it should not be dropped from consideration. Viewing the choice as a binary between heap and full sort alone means missing the option that most often wins in practice.

7. Production Scaling

When scaling out to multiple workers, a Partition-local Top-K -> Global Top-K merge structure is a natural fit.

Suppose 8 workers each handle 10 million requests.

Bad structure:

All 80 million samples
→ central server
→ Global Heap

Good structure:

Worker 1:
10,000,000
-> Top 100

Worker 2:
10,000,000
-> Top 100

...

Worker 8:
10,000,000
-> Top 100

Coordinator:
800개
-> Top 100 again

The central server only needs to examine 800 entries, not 80 million.

TypeScript:

export function mergePartitionTopK(
  partitions:
    readonly (
      readonly LatencySample[]
    )[],
  limit: number,
): readonly LatencySample[]
{
  const global =
    new BoundedTopKLatency(
      limit,
    );

  for (const partition of partitions) {
    addPartition(
      global,
      partition,
    );
  }

  return global.finish();
}

function addPartition(
  global: BoundedTopKLatency,
  partition:
    readonly LatencySample[],
): void
{
  for (const sample of partition) {
    global.add(sample);
  }
}

Each worker uses the same implementation.

export function selectPartitionTopK(
  samples:
    readonly LatencySample[],
  limit: number,
): readonly LatencySample[]
{
  const topK =
    new BoundedTopKLatency(
      limit,
    );

  for (const sample of samples) {
    topK.add(sample);
  }

  return topK.finish();
}

In model-based testing, the bounded heap result is compared against a slow but simple full-sort reference implementation.

import assert from "node:assert/strict";
import test from "node:test";

test(
  "Bounded Top-K produces the same result as a full-sort baseline model",
  () =>
{
    const random =
      createDeterministicRandom(
        0x5eed,
      );

    for (
      let iteration = 0;
      iteration < 1_000;
      iteration += 1
    ) {
      const sampleCount =
        random() % 2_000;
      const limit =
        random() % 100;
      const samples =
        createSamples(
          sampleCount,
          random,
        );

      const actual =
        selectPartitionTopK(
          samples,
          limit,
        );
      const expected =
        referenceTopK(
          samples,
          limit,
        );

      assert.deepEqual(
        actual,
        expected,
      );
    }
  },
);

test(
  "Merging partitioned Top-K results is equivalent to a global Top-K",
  () =>
{
    const random =
      createDeterministicRandom(
        1234,
      );
    const samples =
      createSamples(
        20_000,
        random,
      );
    const partitions =
      partition(
        samples,
        8,
      );

    const local =
      partitions.map(
        (values) =>
          selectPartitionTopK(
            values,
            100,
          ),
      );

    const merged =
      mergePartitionTopK(
        local,
        100,
      );

    const expected =
      referenceTopK(
        samples,
        100,
      );

    assert.deepEqual(
      merged,
      expected,
    );
  },
);

test(
  "Latency ties are broken by `requestId`",
  () =>
{
    const samples:
      readonly LatencySample[] =
    [
      {
        requestId: 30n,
        latencyMicros: 5_000,
      },
      {
        requestId: 10n,
        latencyMicros: 5_000,
      },
      {
        requestId: 20n,
        latencyMicros: 5_000,
      },
    ];

    assert.deepEqual(
      selectPartitionTopK(
        samples,
        2,
      ),
      [
        {
          requestId: 10n,
          latencyMicros: 5_000,
        },
        {
          requestId: 20n,
          latencyMicros: 5_000,
        },
      ],
    );
  },
);

function referenceTopK(
  samples:
    readonly LatencySample[],
  limit: number,
): readonly LatencySample[]
{
  return [...samples]
    .sort(
      (left, right) =>
        -compareLatencyRank(
          left,
          right,
        ),
    )
    .slice(
      0,
      limit,
    );
}

function createSamples(
  count: number,
  random: () => number,
): readonly LatencySample[]
{
  return Array.from(
    { length: count },
    (_, index) => ({
      requestId:
        BigInt(index + 1),
      latencyMicros:
        random() % 100_000,
    }),
  );
}

function partition<T>(
  values: readonly T[],
  count: number,
): readonly (
  readonly T[]
)[]
{
  const result:
    T[][] =
      Array.from(
        { length: count },
        () => [],
      );

  for (
    let index = 0;
    index < values.length;
    index += 1
  ) {
    result[
      index % count
    ].push(
      values[index],
    );
  }

  return result;
}

function createDeterministicRandom(
  seed: number,
): () => number
{
  let state =
    seed >>> 0;

  return () =>
  {
    state = (
      Math.imul(
        state,
        1_664_525,
      )
      + 1_013_904_223
    ) >>> 0;

    return state;
  };
}

A benchmark should not simply ask "is the heap faster?"

Comparison:
1. full sort
2. bounded min-heap
3. partition local Top-K + merge
4. Language-specific standard Top-K helpers

Variables:
N
K
K/N
Number of partitions
Tie ratio
Element size
Ranking computation cost
Whether the input source is streaming

Observations:
Total execution time
peak memory
Number of allocations
retained bytes
Number of comparisons
Merge cost

Just as the Python documentation explicitly notes that nlargest() is especially well-suited for small n, the choice of Top-K implementation ultimately comes down to validating against real workloads that include actual values of N, K, and element cost. ([Python documentation]²)

A personal note: the production scaling description is a case study, nothing more. The actual Python code has been battle-tested in production, but the scaling portion is a theoretically ideal case.

8. Comparison Notes: C++ / Python / C# / TypeScript

C++

The C++ standard heap algorithms bound the number of comparisons performed by push_heap and pop_heap over a random-access range to be proportional to the logarithm of the heap size. std::priority_queue is a container adaptor that uses these heap operations. The actual runtime must account for both the comparison function cost and the cost of the underlying container. (¹)

Small value structs:

requestId
latencyMicros

storing them directly makes it easy to take advantage of a contiguous underlying container without object allocation.

On the other hand:

std::shared_ptr<FullRequest>

inserting them means the actual retained memory may not be small at all, even though the algorithmic memory is O(K).

In C++, a comparator must satisfy strict weak ordering, so you should be especially careful to avoid mutable keys or NaN-like unordered scores.

Python

heapq manages a Python list as a min-heap and provides operations such as heappush, heappop, heapreplace, heappushpop, and nlargest. The official documentation describes heapreplace() as the appropriate operation for a fixed-size heap and specifies that the minimum element can be accessed via heap[0]. ([Python documentation]²)

Note, however, that the cost of looping over Python objects tens of millions of times can exceed the heap arithmetic itself.

If your data already exists as NumPy or PyArrow columns, you should always compare the Python-level heap loop against a native selection kernel.

C#

.NET's PriorityQueue<TElement,TPriority> is a quaternary min-heap where the lowest priority is dequeued first. Because it does not guarantee FIFO for equal priorities, the safer approach is to embed deterministic tie-breaking directly in TPriority itself, as shown in this example. ([Microsoft Learn]⁴)

The ability to separate TElement from TPriority is also useful.

Element:
LatencySample

Priority:
RankKey

Setting it this way lets you keep the business data separate from the heap ordering semantics.

EnqueueDequeue() performs insert-then-extract as a single heap operation, and Microsoft notes that it is generally more efficient than a separate enqueue followed by a dequeue. ([Microsoft Learn]⁵)

TypeScript

This implementation writes the binary heap by hand, but in production the critical piece is not the heap class itself but the comparator contract.

negative
→ worse
positive
→ better

that rule is fixed in one place.

In TypeScript, objects are references, so it is important to maintain a readonly API and ownership rules to prevent external mutation of the ranking fields of any LatencySample that has been inserted into the heap.

Additionally, because requestId requires precise integer comparison for ranking tie-breaking, this example uses bigint.

This post implements the binary heap by hand in order to explain the data structure. The practical choice is different. JavaScript and TypeScript have no standard-library heap, so Node.js projects typically reach for a well-tested package such as heap-js or fastpriorityqueue. Writing your own implementation makes it easy to introduce silent bugs in sift logic or boundary handling in #findSmallerChild, and those bugs tend to manifest as Top-K results that are "plausibly" wrong, making them slow to detect. If you do decide to implement your own, at minimum add model-based tests that cross-check results against a full-sort reference implementation, as shown in section 7 of this post.

Comparator expression differences

C++:

bool better(left,right)

format.

Python:

Natural ordering of HeapItem

was mapped.

C#:

RankKey.CompareTo()

was configured so that the lower priority becomes the root.

TypeScript:

compare(left,right)
< 0  -> worse
> 0  -> better

was used.

The syntax differs, but the shared meaning is one.

Heap Root
=
Currently retained in Top-K
the worst element

Memory differences

C++'s small value objects and C# value structs can be stored directly in the heap's internal storage.

In Python and TypeScript, the heap generally holds object references.

In managed languages, the following distinction can become more significant.

small summary object
vs
large request object

For Top-K, what matters more than the fact that the data structure holds only K elements is what those K elements own.

Common contract

Rank:
(latency DESC, requestId ASC)

Heap:
size <= K

Root:
worst among current Top-K

Candidate:
better(candidate, root)
→ replace

Final Output:
Do not use internal heap order
→ sort only the K items

Ownership:
compact immutable summary

Parallel:
local Top-K
→ global Top-K

Local K:
greater than or equal to global K

finish() re-invocation:
C++ destructive, &&-qualified
lvalue call is disallowed, but can be re-invoked with std::move(...)
second result after first call is empty
C# Destructive (emptied via Dequeue)
Python·TypeScript non-destructive (copy)

9. Further considerations

• When K = 100 and N = 100 million, should the heap hold only the request summary, or should it also pre-retain some trace metadata needed to generate the final report?

• If 1,000 local workers each send their Top-100 results, is it sufficient for the coordinator to heap-process those 100,000 entries again, or is it worth introducing a hierarchical Top-K reduction tree?

• In a system where identical latencies are frequent, does using requestId as a tie-breaker align with the business semantics, or is a separate deterministic key such as a timestamp or sequence number needed?

• If K varies widely at runtime, from 10 to one million, should you keep using a single heap implementation, or does the situation call for a policy that selects between full sort, partition selection, and heap based on K/N?

• If a retained request is a mutable object that may be modified later, should you copy a snapshot summary, or store only an immutable event ID and re-query after the result is finalized?

• If Top-K must be maintained over a rolling 5-minute window, can an append-only bounded heap still be used, or does the requirement call for a different data structure that supports removing expired elements?

A personal note: for that last question, here is one suggested direction. A fixed-size min-heap is structurally ill-suited for time-based expiration. The reason was already covered in Section 5. The heap is cheap precisely because only the root needs to be known; but an element leaving the window can reside anywhere inside the heap, and a standard priority queue or heap interface does not track the position of arbitrary elements, so it cannot delete an element identified only by its identity in O(log K).

You must either use an indexed heap that separately tracks element positions, or move entirely to a balanced BST or ordered set that supports both deletion and rank queries. For special cases like sliding window maximum, where expiration always happens in insertion order, a monotonic deque-based two-queue algorithm is better at O(1) amortized cost. The moment the requirement shifts from append-only to windowed operation, it is correct to revisit the data structure choice rather than forcing this post's heap to stretch beyond its design.

10. Summary

• When K << N, maintaining a min-heap of size K instead of sorting the entire dataset yields an exact Top-K in O(N log K) time and O(K) memory. The C++ standard bounds the number of comparisons for heap push/pop to the logarithm of the heap size. Note, however, that this is an upper bound, not the actual expected cost; see the items below for that. ¹

• In Top-K largest selection, the heap root must be the worst element among the current Top-K, not the best.

• Do not rely on container stability to handle ties; instead, include a tie-breaker such as an immutable ID in the ranking contract. Neither Python's heap nor .NET's PriorityQueue should be assumed to provide automatic stability for equal-priority elements. ([Python documentation]²)

• The heap's internal structure is not a sorted result, so sort the K elements separately at the end.

• When K approaches N, a heap is not automatically the best choice; full sort and partition selection should be benchmarked as alternatives. The official Python documentation also states explicitly that sorting may be more appropriate for large n. ([Python documentation]²)

• In a distributed environment, collecting only each partition's Local Top-K and then performing another Top-K pass is sufficient to obtain the exact Global Top-K, making local reduction more natural than a shared global heap.

Quick memory aid:

If you only need the top K elements,
don't sort all N elements.

Keep only the current K winners,
and place the weakest of them at the root.

Replace it only when a new candidate is stronger than the root.

The essence of Top-K selection is not
"finding the best quickly,"
but "always knowing the weakest winner to eliminate."

References

• C++ standard heap operations

• Python heapq documentation

• C++ standard priority_queue

• .NET PriorityQueue<TElement,TPriority>

• .NET EnqueueDequeue