K-Way Merge Heap

Description

k sorted sequences - log files sorted by time, sorted runs of an external sort, sorted results from k database shards - must become one sorted sequence. Concatenating and sorting ignores the order you already have and needs everything in memory at once. Only the front of each sequence can ever be next.

This skill covers the k-way merge: a heap holding one candidate per sequence, each tagged with where it came from, so N values merge in O(N log k) time with O(k) memory. The same frontier also finds the smallest range that touches every list.

We'll go from simple to more technical:

1. The pattern: seed the heap with each sequence's first value, pop the minimum, push its successor.
2. A second flavor: the smallest range covering k lists, found by advancing the minimum's list.
3. Where k-way merges run (external sorts, LSM-tree compaction, sharded queries).
4. What breaks it: empty sequences, loading everything, lost origins, overflowing comparators.

The approach

int[] mergeKArrays(int[][] arrays) {
    PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));  // {value, array, index}
    int total = 0;
    for (int i = 0; i < arrays.length; i++) {
        total += arrays[i].length;
        if (arrays[i].length > 0) heap.offer(new int[]{arrays[i][0], i, 0});   // skip empty arrays
    }
    int[] out = new int[total];
    int pos = 0;
    while (!heap.isEmpty()) {
        int[] top = heap.poll();
        out[pos++] = top[0];
        int arr = top[1], next = top[2] + 1;
        if (next < arrays[arr].length) heap.offer(new int[]{arrays[arr][next], arr, next});
    }
    return out;
}

import heapq


def merge_k_arrays(arrays: list[list[int]]) -> list[int]:
    heap = [(arr[0], i, 0) for i, arr in enumerate(arrays) if arr]   # (value, array, index); skip empty arrays
    heapq.heapify(heap)
    out = []
    while heap:
        value, arr, idx = heapq.heappop(heap)
        out.append(value)
        if idx + 1 < len(arrays[arr]):
            heapq.heappush(heap, (arrays[arr][idx + 1], arr, idx + 1))
    return out

# heapq.merge(*arrays) is the same merge as a lazy iterator

The heap holds at most one entry per sequence - the smallest value not yet emitted from each - so the overall minimum is always at the root. Each entry carries its origin, which says where the replacement comes from. N values cost O(N log k) time and O(k) heap memory. Empty sequences must be skipped when seeding, and the comparator uses Integer.compare: x[0] - y[0] overflows once values span more than about 2^31. In Python, tuple entries (value, array, index) compare without any comparator to get wrong - and heapq.merge(*arrays) is this whole pattern as a lazy iterator.

A second flavor: the smallest range that touches every list

With the same one-candidate-per-list heap, you can find the smallest range [a, b] containing at least one value from each of k sorted lists. The heap's entries always cover every list, so [heap minimum, current maximum] is a valid range; to find a narrower one you must raise the minimum, so advance the list that holds it:

while (true) {
    int[] top = heap.poll();                                   // current minimum, with its list and index
    if (max - top[0] < bestHi - bestLo) { bestLo = top[0]; bestHi = max; }   // strictly narrower
    if (top[2] + 1 == lists.get(top[1]).size()) break;        // that list is used up: no range can cover it now
    int next = lists.get(top[1]).get(top[2] + 1);
    heap.offer(new int[]{next, top[1], top[2] + 1});
    max = Math.max(max, next);
}

while True:
    value, i, j = heapq.heappop(heap)                        # current minimum, with its list and index
    if max_val - value < best_hi - best_lo:                  # strictly narrower
        best_lo, best_hi = value, max_val
    if j + 1 == len(lists[i]):
        break                                                # that list is used up: no range can cover it now
    nxt = lists[i][j + 1]
    heapq.heappush(heap, (nxt, i, j + 1))
    max_val = max(max_val, nxt)

Only the minimum can be improved: every range starting at it must reach max anyway. When the list holding the minimum runs out, stop - any later range would have to skip that list. Updating only on a strictly narrower range keeps the smallest start among ties, because minima are visited in increasing order.

Where you'll see it

External merge sort (databases sorting more data than fits in memory, sort on huge files) sorts chunks, writes them as runs, and k-way merges the runs. LSM-tree databases (LevelDB, RocksDB, Cassandra) merge sorted SSTables during compaction the same way, and a distributed query merges sorted shard results before returning the top rows.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does the heap never hold more than k entries?

2. What does each heap entry need besides the value, and why?

3. In the smallest-range search, why advance the list holding the minimum and stop when it runs out?

Key takeaways

• One heap entry per sequence: value plus origin. O(N log k) time, O(k) memory.
• Skip empty sequences; compare with Integer.compare.
• The same heap finds the smallest range covering k lists: advance the minimum's list, stop when it runs out.
• This is how external sorts and LSM-tree compactions merge sorted runs.