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

Only the smallest unconsumed value from each sorted feed can be the next global value. Emitting it exposes one replacement from that same feed. Heap entries therefore carry value, feed index, and offset.

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.

type Cursor struct{ Value, Feed, Offset int }
feeds := [][]int{{1, 7}, {2, 4}, {1, 8}}
// Suppose the min-heap has just returned its smallest cursor.
next := Cursor{Value: 1, Feed: 0, Offset: 0}
next.Offset++
if next.Offset < len(feeds[next.Feed]) {
	next.Value = feeds[next.Feed][next.Offset]
	fmt.Println(next) // {7 0 1}: the replacement offer for this feed.
}

A small frontier instead of one large sort

A heap is a partial order: the root is minimal; siblings need not be sorted. Go's container/heap expects a type implementing Len, Less, Swap, Push, and Pop. Be careful that Pop removes the last element after heap repair. Merging sorted logs or runs avoids sorting all N values again. Empty feeds still cost inspection time.

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.

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