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

Sorted feeds expose only their next unconsumed value as a candidate. A min-heap stores (value, feed_index, element_index) for each active feed. After extracting the minimum, advance only that feed. Other feeds already have their cheapest remaining values represented.

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.

using Candidate = std::tuple<Int, std::size_t, std::size_t>;
std::vector<std::vector<Int>> feeds{{1, 7}, {2, 4}, {1, 8}};
std::priority_queue<Candidate, std::vector<Candidate>, std::greater<>> frontier;
for (std::size_t feed = 0; feed < feeds.size(); ++feed) {
    frontier.emplace(feeds[feed][0], feed, 0);
}
auto [value, feed, position] = frontier.top();
frontier.pop();
std::cout << value << ' ' << feed << '\n'; // 1 0: source breaks the tie.
if (++position < feeds[feed].size()) {
    frontier.emplace(feeds[feed][position], feed, position);
}
std::cout << std::get<0>(frontier.top()) << '\n'; // The other 1 is still present.

A small frontier instead of one large sort

priority_queue is a max-heap by default; forgetting the comparator reverses output order. Tuple tie breakers make equal values deterministic without discarding duplicates. Empty feeds contribute no candidate but still require inspection. For N total values and K feeds, initialization inspects O(K) feeds, and output costs O(N log(K+1)) with at most K candidates. Concatenate-and-sort is simpler but discards the useful sorted-feed structure and requires sorting all N values. Holding const references prevents accidental destructive consumption of the feed vectors.

For N records across K feeds, inspecting the feeds costs O(K), then heap work costs O(N log(K+1)). The frontier uses O(K) space beyond output. The K term matters when many feeds are empty. For only two feeds, a two-pointer merge is often simpler.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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