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

Merge sorted feeds while preserving duplicate values and leaving every feed unchanged. The next globally smallest value must be one of the current feed heads.

Concatenating and sorting ignores useful order already present in each input. A heap frontier stores one active candidate per feed, so each emitted value reveals only one new candidate instead of rescanning all feeds.

Offering one entry from each feed

For feeds [1, 7], [2, 4], and [1, 8], offer 1, 2, 1. Emit a 1 and replace only its offer with 7; the other 1 must still be emitted. Store the source and position alongside the timestamp so ties are deterministic and the correct feed advances. Equal timestamps are separate log records, not duplicates to remove.

The heap contains one current candidate per active sorted feed. Removing the smallest candidate reveals exactly one replacement from its feed. A heap entry needs the value and source position; equal values must not lose multiplicity. Final O(k+N log(max(2,k))) time including inspecting all feeds, O(k) frontier plus output.

A heap entry carries source coordinates, and an explicit comparator gives deterministic handling of equal values:

import java.util.*;

class Example {
    public static void main(String[] args) {
        record Cursor(long value, int feed, int offset) {}
        var frontier = new PriorityQueue<Cursor>(Comparator
            .comparingLong(Cursor::value).thenComparingInt(Cursor::feed));
        frontier.add(new Cursor(1, 2, 0));
        frontier.add(new Cursor(1, 0, 0));
        assert frontier.remove().feed() == 0;
        assert frontier.size() == 1;
    }
}

The two entries are both retained. The source coordinates identify which feed to advance after removing one entry. Tie-breaking is not permission to deduplicate equal values, and empty feeds still need inspection during initialization.

A small frontier instead of one large sort

K-way merge is useful for merging sorted file runs, shard results, and ordered event feeds. Keep frontier size proportional to active sources rather than total output size.

Every feed is sorted nondecreasingly. Return all values sorted with duplicates preserved. Empty feeds and empty outer input are valid. Never change an inner feed or the outer list; no sortedness validation is required.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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