Heaps & Priority Queues

Almost all of it goes to the counting phase. Ranking terms by frequency needs a count for every one of the 10 million distinct terms held at once; the size-50 heap adds fifty entries. The heap bounds the output, not the memory.

Repairing only the max-heap-too-large case lets the min-heap grow without limit whenever samples arrive above the current median, so the max-heap keeps an old small value on top and the reported median sinks toward it. Both repair directions are required.

Heaps remove only their top, so expiring samples are deleted lazily: mark the departing value as pending removal, track logical sizes separately from physical heap sizes, rebalance on the logical counts, and discard stale tops before reading the median.

Only the bounded candidate heap survives. It sees each record once and holds O(k) state, so an answer is available at any moment. Sorting and quickselect are offline: both need the entire input materialized with random access.

The sinking element's map entry goes stale, so a later reprioritization by identity resolves to the wrong array slot and mutates a different element's key. Nothing fails at the moment of the bug; the damage surfaces much later.

A size-k heap commits you to one frozen question. Bounded state and a single pass let the job run under the cap, but every value that lost to the bar is destroyed, so a different k or metric means re-ingesting the stream.

Commit to one default with a documented, measured threshold rather than three tuned paths. As k approaches n, O(n log k) converges on O(n log n) and the candidate structure holds O(n) items — above the crossover, just sort.

Composite keys compare component by component, so when priority and sequence both tie, the queue falls through to comparing payloads — and payload records with no defined ordering make that comparison fail. A strictly unique sequence number stops the fall-through.

Replace-top overwrites the root with the new key and runs a single sift-down. Extract-then-insert runs a sift-down to repair the removal and then a sift-up for the arrival — about twice the tree traversal, plus a needless shrink and regrow of the structure.

Same asymptotics, much better constants. The implicit layout stores only keys, contiguously: no child or parent references, no per-node allocation, and navigation is arithmetic rather than a dependent memory load, so the hot top levels stay resident in cache.

Memory bounds the fan-in, not comparison cost. Comparisons grow as log k, but every open source needs a resident read buffer, so memory grows linearly in k. Take the largest k whose per-source buffers still read efficiently.

An exact two-heap median keeps every sample forever, so memory grows without bound per endpoint per instance, and two instances' results cannot be combined into a global median. Under a fleet memory ceiling, prefer a bounded window or a mergeable quantile sketch.

Ask what share of runtime the priority queue owns and how decrease-keys compare with extractions. Fibonacci heaps win on paper, but their pointer overhead and cache behaviour usually lose to an array-backed indexed heap on real inputs.