ExampleDifficulty: Intermediate3 min

Heap Patterns Example: Merging k Sorted Lists With One Item From Each

Keep only the front item of each list in a min-heap: the smallest of them is the next item of the merged list, and its successor takes its place.

Merging k sorted lists needs only the front item of each list in a min-heap, because the next item of the merged list is always the smallest of those fronts. Three lists, A = 2 9 14, B = 1 7 15 20 and C = 5 6, are to become one sorted list. Comparing every front on every step costs O(k) a step, and gluing the lists together and sorting throws away the order they already have. The heap holds k items, one per list, and finds the smallest in O(log k).

Each heap entry carries the value, the list it came from and its position there, so a popped value knows which item replaces it. When a list runs out, nothing replaces its item and the heap shrinks. The steps list each heap's entries smallest first, written value/list.

Merging 2 9 14, 1 7 15 20 and 5 6

Pop 1: the smallest front, 1 from B

text

heap:   1/B 2/A 5/C
popped: 1 from B, then 7/B pushed
merged: 1

Pop 2: 2 from A

text

heap:   2/A 5/C 7/B
popped: 2 from A, then 9/A pushed
merged: 1 2

Pop 3: 5 from C

text

heap:   5/C 7/B 9/A
popped: 5 from C, then 6/C pushed
merged: 1 2 5

Pop 4: C runs out

text

heap:   6/C 7/B 9/A
popped: 6 from C, which is now empty
merged: 1 2 5 6

Pop 5: 7 from B

text

heap:   7/B 9/A
popped: 7 from B, then 15/B pushed
merged: 1 2 5 6 7

Pop 6: 9 from A

text

heap:   9/A 15/B
popped: 9 from A, then 14/A pushed
merged: 1 2 5 6 7 9

Pop 7: A runs out

text

heap:   14/A 15/B
popped: 14 from A, which is now empty
merged: 1 2 5 6 7 9 14

Pop 8: 15 from B

text

heap:   15/B
popped: 15 from B, then 20/B pushed
merged: 1 2 5 6 7 9 14 15

Pop 9: the last item

text

heap:   20/B
popped: 20 from B, which is now empty
merged: 1 2 5 6 7 9 14 15 20

The listing is the whole merge. Its entries hold the list's number rather than its letter, and a list that starts empty contributes no entry.

merge_k.pypy

import heapq


def merge_k(lists: list[list[int]]) -> list[int]:
    heap = [(items[0], index, 0) for index, items in enumerate(lists) if items]
    heapq.heapify(heap)
    merged: list[int] = []
    while heap:
        value, index, position = heapq.heappop(heap)
        merged.append(value)
        if position + 1 < len(lists[index]):
            heapq.heappush(heap, (lists[index][position + 1], index, position + 1))
    return merged


print(merge_k([[2, 9, 14], [1, 7, 15, 20], [5, 6]]))
print(merge_k([[4, 4], [], [4]]))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

[1, 2, 5, 6, 7, 9, 14, 15, 20]
[4, 4, 4]

The second run merges lists holding equal values. Python compares tuples field by field, so two entries with the same value are ordered by their list number and never reach the position; in Java the comparator has to say so explicitly. Every one of the n items is pushed and popped once in a heap of at most k entries, so the merge is O(n log k) time and O(k) extra space besides the output. Sorting all n items together costs O(n log n), and the gap grows when there are many items and few lists.

Heaps

← → move through sections and cards