Heaps and k-way merge

An incident viewer combines timestamped logs from several services. Each service's export is already sorted. Concatenating everything and sorting again works, but throws away that useful input order and requires collecting the whole result first.

The next entry can only be the first unread entry of one feed. A min-heap lets the viewer compare those few candidates, then advance just the feed that supplied the winner.

Merging logs that are already sorted

K-way merge combines already sorted feeds while preserving duplicates. Concatenating and numerically sorting all values is a straightforward baseline, but it discards the useful fact that each feed already reveals its cheapest remaining value.

Keep one candidate from each nonempty feed in a min-heap. The global next value must be among those candidates: every hidden value lies behind a feed's current head and cannot be smaller than that head.

Offering one entry from each feed

Represent a candidate with its value, feed index and position within that feed. Extracting it emits the value, then replaces only that feed's candidate with its next value. Never discard equal values: duplicate output values may belong to the same or different feeds.

A heap is a partially ordered array, not a fully sorted collection. For a zero-based binary heap, parent index is floor((i-1)/2) and children are 2i+1 and 2i+2. Insertion bubbles a candidate up; removing the root moves the last candidate to the root and repairs downward. JavaScript has no built-in standard priority queue, so implementing that small heap is part of the final stage.

Tie-breaking by feed and position makes internal behavior deterministic without requiring objects to be implicitly comparable. Array comparison in JavaScript is not a lexicographic numeric comparator; compare the fields explicitly. Read input by positions rather than destructively shifting feeds.

const feed = [1, 4, 8];
const candidate = {value: feed[0], feedIndex: 2, position: 0};
console.log(candidate.value, feed[candidate.position + 1]); // 1 4
console.log(feed); // [1, 4, 8]: candidate tracking leaves input intact

A small frontier instead of one large sort

For N values across K feeds, inspect all K feeds and then perform O(N log(K+1)) heap work; the frontier has at most K candidates. A heapify build can initialize in O(K), while repeated insertion costs O(K log(K+1)) for active candidates. Returned values take O(N) output storage. This is useful for sorted logs and sorted shard results; unsorted feeds violate the invariant and need sorting first.

The incident viewer can emit the winning entry and ask only that feed for its successor.