Fixed-Size Min-Heap Based Top-K Selection
If you only need the 100 slowest requests out of tens of millions, sorting everything does far more work than the requirement demands. All you need is to keep only the candidates that qualify for the top K. By maintaining a min-heap of size K with the weakest element among the current top K at its root, you only have to determine whether each new element is stronger than the root.
· Practice memo · 46 min read · Medium
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. 1
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 is simply the harmonic number.
The first term is K rather than K log K, and there is a reason for it. Push a random permutation into the heap one element at a time and the average sift-up distance is O(1), which makes the whole build linear; Hayward and McDiarmid put the average comparison count for Williams's repeated insertion at roughly 2.28K. The worst case is still K log K, but if you only count expected cost it is linear.
For a workload with K << N you can simplify the whole thing to O(N + K log K log(N/K)). With N at 50 million and K at 100, the expected number of updates is about 1,312, and most of the remaining input is dropped after 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: what trips beginners up most is the direction of a min-heap versus a max-heap. The reason you use a min-heap to find the K largest is the cutoff (the defensive line, the CutOff).
Put latency alone in the comparator, though, and production results start to wobble: when several requests share the same latency, which one stays in the Top-K comes down to container stability.
The Python heapq docs say the same: heap sort is not stable, and equal-priority items may need their own tie-breaker. The .NET PriorityQueue does not guarantee FIFO for elements with equal priority either.
Accordingly, this example defines (latencyMicros DESC, requestId ASC) as a complete ranking contract. ([Python documentation]2)
One prerequisite comes with this: requestId has to be unique for the result to be a total order. Duplicate IDs make the comparator return false in both directions, so the two elements are equivalent and which one survives is up to the implementation again. If your system does at-least-once delivery, retries, or client-generated IDs, you need a third key such as a receive sequence.
Workloads like streaming telemetry (I could not find a Korean word for it), log analysis, leaderboard candidate extraction, and anomaly ranking fit it well: K << N, and there is no need to keep the whole input. Conversely, when K gets close to N, maintaining the heap stops paying off. The official Python docs say as much: nlargest/nsmallest win for small n, while for large n a full sort may suit better.
A top-K heap is the right tool when the ratio of input size to K justifies the choice (2)
In production, what you put into the heap matters more. Stuff the request body, response body, and tracing tree in while hunting the 100 slowest requests and a huge object graph stays pinned in memory even though K is small. You are safer keeping only the immutable key that ranking needs and the minimal summary that final output needs.
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 a day.
Each request only needs to carry the following.
LatencySample
- requestId
- latencyMicrosGoal:
Top 100 Slowest RequestsInput:
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 priorityTherefore:
103 / 8400
105 / 8400
101 / 1250
104 / 910
102 / 82in that order.
With K = 3, the values to keep are:
103 / 8400
105 / 8400
101 / 1250Inside the heap, that element is the root.
101 / 1250Because 101 is the element that has to be evicted first from the current Top-3.
New request:
106 / 500is weaker than the root.
500 < 1250
-> discard immediatelyConversely:
107 / 2200then:
2200 > 1250
-> remove 101
-> insert 107it becomes.
Personal note: this is what I reach for when checking total cost in a defense workload test after a DDoS run. Watching the risk score of each attack candidate as a stream and keeping only the top K in a min-heap means that once a threshold forms, most candidates die on a single comparison with the heap root. It has earned its place in practice.
2. Core Expressions
C++23
In C++, small value objects go into a generic bounded heap, where a single Comparator defines both the final sort order and the heap cutoff semantics.
#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() && blocks calls on lvalues, but it does not consume the object like a linear type, so code that calls std::move(topK).finish() a second time still compiles.
The first call empties the heap, so the second one just returns an empty vector.
Note also that finish() copies elements: std::priority_queue::top() returns const T&, so result.push_back(heap_.top()) never moves.
With the compact value struct this post assumes, K copies do not matter. If you put heavy objects in the heap as Section 5 warns, you pay for them again here. Unwrapping top() with const_cast to move out of it is not guaranteed by the standard, so do not do it; if you need the move, hold a std::vector as the underlying container and call std::pop_heap / pop_back yourself.
The comparator direction in std::priority_queue feels backwards the first time you see it. BetterLatencyRank here expresses the ordering "better elements come first", and once you hand that ordering to a priority queue, top() holds whatever is last in it: the worst retained value.
The complexity argument takes one extra step. The standard's [priority.queue] clause has no separate Complexity paragraph for push and pop; instead it defines 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, 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 comparisons and pop_heap to no more than comparisons. Actual total runtime is also affected by the cost of the comparator and the underlying container. (3, 1)
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]2)
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 exists to make the min-heap root the "worst retained record".
_HeapItem being frozen=True is deliberate: as Section 5 says, changing a ranking field once the item is in the heap breaks the guarantee that the root is the minimum. If only the LatencySample outside the heap is immutable while the thing actually in the heap stays mutable, the code does not enforce that rule. heapq never touches the items themselves, it only swaps list slots, so frozen costs nothing at runtime.
While the heap is not full, a _HeapItem is built and stored. Once it is full, the two fields of LatencySample are compared against the root first, and a _HeapItem is built only when the candidate will actually replace something, so no temporary object is created per rejected input. Retained elements stay O(K), and after the heap fills, _HeapItem construction is proportional to the number of replacements.
On equal latency:
Smaller requestId
→ better
Larger requestId
→ worse
→ should go toward the heap rootTo sum up:
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]4)
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]5)
TypeScript
In TypeScript the ranking contract lives in its own function, with a small binary min-heap underneath.
Comparator rules:
< 0
-> left is worse
> 0
-> left is betterexport 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
Real systems do not drop the whole network DTO into the heap.
Network Event
-> Validation
-> Compact Ranking Record
-> Top-K HeapSay the transport event is much bigger, like this.
export type LatencyEvent =
Readonly<{
requestId: bigint;
durationNanos: bigint;
requestBody?: Uint8Array;
responseBody?: Uint8Array;
headers:
Readonly<Record<string, string>>;
}>;Top-K only needs two values out of all that.
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),
};
}Unit conversion has a trap: durationNanos / 1_000n is BigInt integer division, so it truncates, and 1999ns and 1000ns land on the same 1μs.
Shrinking nanosecond observations to microseconds puts different requests in the same rank bucket, and then the tie-breaker requestId becomes the real sort key. Inside a microsecond bucket at the cutoff, requestId alone decides which element survives. If resolution matters, keep nanoseconds and raise the bound check to uint64.
The responsibilities split like this.
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 itemsIn particular, avoid this structure.
Top-K heap
-> requestBody 5 MiB
-> responseBody 20 MiB
-> header map
-> tracing graphEven with K at 100, you can pin several GiB of object graph.
The better structure looks like this.
Heap:
requestId
latencyMicros
After final Top-K is determined:
requestId
-> query detailed trace if needed4. 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?When to use it is essentially the heart of the algorithm, so I lay it out as the questions below.
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]2)
Therefore:
Heap internal iteration
→ output final rankingis not how you should use it.
If the final output needs the order too:
Full sort of N elementsrather than:
Final sort of only K elementsdo this.
Comparator direction is the most common mistake
Goal:
Top K Largestbut with a max-heap the root becomes the best value.
Then when a new candidate arrives, nothing tells you which element to drop.
For Top-K largest:
min-heapthis is the natural choice.
Conversely, Bottom-K smallest wants a max-heap.
Do not leave tie-breaking to container stability
The ranking used here:
latency DESC
requestId ASCis deliberate.
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]2)
A production comparator should include, wherever possible:
primary score
secondary immutable IDas well.
Do not feed NaN into a floating-point score
In the following comparator:
left.score > right.scorea score = NaN means the ordering relation may not satisfy a proper strict weak ordering.
This example normalizes latency to:
uint32 microsecondsand then ranks.
If the model needs a real-valued score, then at the ingestion boundary:
finite
not NaNyou have to enforce it.
Personal note: right now I use code blocks for the emphasis blocks, and I am not sure that is the right call for visibility. Switching that emphasis to something else is not easy either. Lately I see a lot of widgets styled after the macOS UI, and I keep wondering whether to add one. But the current UI mockup does not fit, so I am not sure how to get readability right for readers.
Do not change a ranking field once it is in the heap
It goes wrong in cases like these.
heap.add(sample)
Afterwards:
sample.latency = ...A heap builds its tree invariant from the comparator result at insertion time.
Change an element's priority from outside and nothing guarantees the root is still the real minimum.
Heap elements are either:
immutable valueor the heap itself has to manage update operations.
This structure suits append-only observations especially well
These workloads:
Keep adding new samples
-> Top-K at the endfit it very well.
On the other hand:
Updating the score of an existing item
Deleting an existing item
Refreshing the priority of an arbitrary itemif these are frequent, a plain bounded heap is the wrong tool.
In that case, look at:
indexed heap
balanced tree
ordered set
Recalculationand other options of that kind.
When K is close to N, a heap is not the obvious answer
For example:
N = 1,000,000
K = 900,000you put nearly every value into the heap and still pay the log K upkeep.
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]2)
In practice:
K << N
→ prioritize bounded heap
K ≈ N
→ benchmark sort / partition selectionis the right call.
With K = 1 you do not even need a heap
If you only need the single slowest request:
running maxone value is enough.
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]2)
K cannot be raised later
Process the stream from the beginning:
K = 100and everything ranked 101st and below has already been thrown away.
Later,
Let's change K to 1000even if you want it, there is no way to recover it.
The choice you need:
source replay
Maintaining from the start with a larger K
Preserving the raw archiveis one of these.
Bounded selection throws information away on purpose.
A heap does not deduplicate
If the same event arrives twice:
request 42
request 42both copies can end up in the Top-K.
Top-K and dedup are separate problems.
Top-K
= ranking selection
Dedup
= identity uniquenessDo not mix the two inside the heap code.
Heavy objects change what K means
Memory complexity is usually written as:
O(K)but the real byte cost is:
O(
K × retainedObjectGraphSize
)in practice.
In C++, putting a shared_ptr<Request> in the heap can keep the request body and the downstream graph alive.
In Python, C#, and TypeScript, holding an object reference in the heap does the same: that object graph stays out of the GC's reach.
So Top-K stores, wherever possible:
compact immutable summarygoes into the heap.
Managed languages add allocation pressure on top of that. Build a fresh wrapper object for each of tens of millions of stream elements and the GC keeps sweeping that garbage even though almost all of it is dropped immediately. That is why the Python implementation, once the heap is full, compares the root against raw fields first and only builds a _HeapItem when a replacement is confirmed, and why the C# implementation uses a readonly struct rather than a class.
If the ranking key is small enough, you can drop the wrapper entirely. Say latencyMicros is a uint32 and requestId fits in a uint32:
packed = (uint64(latencyMicros) << 32) | uint32(requestId)you can pack both into one integer and put only that in the heap. The trick does not survive a tie-break that runs ascending on ID, though: this contract is latency DESC + requestId ASC, so the low 32 bits must hold ~requestId rather than requestId for the min-heap root to be the worst element under the contract. Use bit packing only when you can pin the width and sort direction of every field; if that assumption is not documented, adding one field later breaks it quietly.
Do not parallelize by locking a shared heap
When many workers lock the same heap on every sample:
Worker A ─┐
Worker B ─┼-> lock -> global heap
Worker C ─┘lock contention can cost more 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-Kstill gives exact results.
In a parallel or distributed setting:
local heap
-> mergeis the natural fit.
Local Top-K merging is not an approximation
There is a prerequisite, though: each partition has to keep up to the global K, and if a partition holds fewer elements than the global K, keep all of them. Shrinking the local K below the global K gives wrong results; going above it keeps correctness intact but sends more candidates to the coordinator.
Take an element x in partition P that did not make the local Top-K.
Then inside P there are already:
At least K elements better than xsuch elements.
Those same K elements exist in the global input too.
So x cannot reach the global Top-K either.
That is:
TopK(
Full input
)
=
TopK(
The union of each partition's Top-K results
)holds.
That property is very useful for distributed aggregation.
Without a total ranking, distributed merges wobble too
If you compare latency alone with no tie handling:
Partition A
Partition Bwhich candidate with the same score survives can differ by heap implementation or arrival order.
The more distributed the Top-K gets:
(score, uniqueId)the more a total rank of this shape matters.
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 sample6. Bad Example
Here is the simplest TypeScript implementation.
export function slowestRequestsBad(
samples: LatencySample[],
limit: number,
): LatencySample[]
{
samples.sort(
(left, right) =>
right.latencyMicros
- left.latencyMicros,
);
return samples.slice(
0,
limit,
);
}This is not always bad code.
With a few hundred inputs, this approach is actually simpler and fast enough.
The problem is:
N = 50,000,000
K = 100using it as-is on the same requirement.
First problem:
Sorting all N elements
O(N log N)it does.
What you actually need is:
Maintaining 100 candidatesonly that.
Second, it mutates the input array in place.
samples.sort(...)so the original input order the caller expected is gone.
Third, there is no tie-breaker.
request 10 / 8400
request 20 / 8400The domain contract never says which of the two comes first.
Fourth, the entire input has to be in memory already.
Streaming source:
network
file
generator
database cursorif you only need the Top-K out of 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 heapThird option: partition selection
The partition selection that came up twice earlier is worth unpacking here. It is a selection algorithm that partitions the array, finds only the K-th boundary, and never touches the side it does not need. In C++, std::nth_element provides the operation, though the standard does not require a particular implementation such as introselect. Average comparison complexity for the non-parallel overload is linear; the general worst case is not fixed by the standard.
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 standardThe selection criteria look like this.
Situation | Candidate |
|---|---|
Streaming, input cannot be held | bounded heap |
All data in memory, K is very small | heap or |
All data in memory, K is moderate |
|
K is close to N | full sort |
- Situation
Streaming, input cannot be held
- Candidate
bounded heap
- Situation
All data in memory, K is very small
- Candidate
heap or
nth_element
- Situation
All data in memory, K is moderate
- Candidate
nth_elementis often advantageous
- Situation
K is close to N
- Candidate
full sort
There is a price. nth_element rearranges the input array, so it inherits the mutation problem noted at the top of Section 6. The result is not sorted either, so the K elements need a separate sort, and it is not stable. Even so it belongs in the toolbox: framing the choice as heap versus full sort alone loses the option that wins most often in practice.
7. Production Scaling
Scaling out to multiple workers naturally lands on a Partition-local Top-K -> Global Top-K merge structure.
Say 8 workers each handle 10 million requests.
Bad structure:
All 80 million samples
→ central server
→ Global HeapGood 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 againThe central server only has to look at 800 entries instead of 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 runs 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();
}Model-based tests compare the bounded heap result against a slow but simple full-sort reference.
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 does not just 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 costJust 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]2)
Personal note: the production scaling section is a case study and nothing more. The Python code has been through real production, but the scaling part is an ideal case that only exists on paper.
8. Comparison Notes: C++ / Python / C# / TypeScript
Language | Heap representation | Root | Element storage | Pitfalls |
|---|---|---|---|---|
C++ |
| Cutoff based on comparator | Value type | Comparator direction |
Python |
| Minimum item | Python object | Ties and object overhead |
C# |
| Minimum priority | Element + priority | equal priority unstable |
TypeScript | direct binary heap | comparator minimum | object reference | ownership and implementation verification |
- Language
C++
- Heap representation
std::priority_queue- Root
Cutoff based on comparator
- Element storage
Value type
- Pitfalls
Comparator direction
- Language
Python
- Heap representation
heapq+list- Root
Minimum item
- Element storage
Python object
- Pitfalls
Ties and object overhead
- Language
C#
- Heap representation
PriorityQueue<T,P>- Root
Minimum priority
- Element storage
Element + priority
- Pitfalls
equal priority unstable
- Language
TypeScript
- Heap representation
direct binary heap
- Root
comparator minimum
- Element storage
object reference
- Pitfalls
ownership and implementation verification
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. (1)
Small value structs:
requestId
latencyMicrosstored directly, they make it easy to use a contiguous underlying container with no object allocation.
Conversely:
std::shared_ptr<FullRequest>with them in the heap, retained memory can be far from small even though algorithmic memory is O(K).
In C++, a comparator has to satisfy strict weak ordering, so mutable keys and NaN-like unordered scores are the things to avoid.
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]2)
The cost of looping over Python objects tens of millions of times can outweigh the heap arithmetic, though.
If the data already sits in NumPy/PyArrow columns, always benchmark 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]4)
Being able to separate TElement from TPriority is useful too.
Element:
LatencySample
Priority:
RankKeyThat split keeps the business data apart 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]5)
TypeScript
This implementation writes the binary heap by hand, but in production the point is not the heap class itself but the comparator contract.
negative
→ worse
positive
→ betterrule is fixed in one place.
Objects in TypeScript are references, so keep a readonly API and ownership rules that stop anyone from mutating the ranking fields of a LatencySample that is already in the heap.
requestId also needs exact integer comparison for ranking tie-breaks, which is why this example uses bigint.
The binary heap is hand-written here to explain the data structure; the real-world choice is different. JavaScript and TypeScript ship no heap in the standard library, so Node.js projects usually take a proven package such as heap-js or fastpriorityqueue. A hand-rolled sift loop invites quiet bugs, an off-by-one or the boundary handling in #findSmallerChild, and those bugs show up as Top-K results that are wrong in a plausible way, so you find them late. If you do write your own, at least pair it with a model-based test against a full-sort reference, as in section 7.
Comparator expression differences
C++:
bool better(left,right)form.
Python:
Natural ordering of HeapItemwas mapped as.
C#:
RankKey.CompareTo()is arranged so the lower priority becomes the root.
TypeScript:
compare(left,right)
< 0 -> worse
> 0 -> betterwas used.
The syntax differs; the shared meaning is the same.
Heap Root
=
Currently retained in Top-K
the worst elementMemory differences
C++ small value objects and C# value structs can be stored directly in the heap's internal storage.
In Python and TypeScript the heap usually holds object references.
In managed languages the following difference can matter more.
small summary object
vs
large request objectWhat matters in Top-K is not that the structure holds only K elements but 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
With
K = 100andN = 100 million, does the heap hold only the request summary, or do you pre-retain some of the trace metadata the final report needs?If 1,000 local workers each send a Top-100, is it enough for the coordinator to heap-process those 100,000 entries, or is a hierarchical Top-K reduction tree worth it?
In a system where identical latencies are common, does
requestIdas a tie-breaker match the business meaning, or do you need a separate deterministic key such as a timestamp or sequence?K swings from 10 to a million at runtime; do you keep one heap implementation anyway, or do you need a policy that picks full sort, partition, or heap by
K/N?If a retained request is mutable and can change later, do you copy a snapshot summary, or store only the immutable event ID and re-query once the result is final?
If Top-K has to cover a rolling 5-minute window, can an append-only bounded heap still do it, or does that need a different structure that can remove expired elements?
Personal note: one direction for that last question. A fixed-size min-heap is structurally weak against time-based expiry. The reason came up in Section 5. The heap is cheap because you only need to know the root, but an element leaving the window can sit anywhere inside it, and a normal priority queue or heap interface does not track where arbitrary elements are, so it cannot delete an element given only its identity in O(log K).
You would use an indexed heap that tracks element positions, or move all the way to a balanced BST or ordered set that gives you deletion and rank lookup together. Where expiry always follows insertion order, as in sliding window maximum, a monotonic deque two-queue algorithm does better at
O(1)amortized. The moment the requirement turns from append-only into a window, the right move is to pick the data structure again, not to stretch this post's heap.
10. Summary
When
K << N, maintaining a min-heap of size K instead of sorting the entire dataset yields an exact Top-K inO(N log K)time andO(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. 1In Top-K largest, the heap root must be the worst element of 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
PriorityQueueshould be assumed to provide automatic stability for equal-priority elements. ([Python documentation]2)The heap's contents are not a sorted result, so sort just the K elements 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]2)In a distributed setting, gathering each partition's Local Top-K and running Top-K once more still yields the exact Global Top-K, so local reduction beats 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
Footnotes
- [[alg.heap.operations]](https://eel.is/c%2B%2Bdraft/alg.heap.operations) ↩
- heapq — Heap Queue Algorithm — Python Documentation ↩
- [[priority.queue]](https://eel.is/c%2B%2Bdraft/priority.queue) ↩
- PriorityQueue<TElement,TPriority> Class | Microsoft Learn ↩
- * PriorityQueue<TElement,TPriority>.EnqueueDequeue Method | Microsoft Learn ↩