Lesson 38 — Heap II: k queues, one heap

Day 47 · ~20 minutes · heap invariant · Python

Tonight's problem is Merge k Sorted Lists. In interviews, this is the moment where "I can merge two sorted lists" must grow into "I can manage many sorted frontiers at once." The trap is re-checking every list head again and again. The win is letting one heap remember the best current head for you.

The invariant

The heap holds one head per list; pop the smallest, push its successor, repeat until every list is drained.

That's the whole pattern. Each sorted list behaves like a queue: only its current head is eligible to be the next answer. A min-heap keeps those eligible heads ordered, so the smallest available node is always the next node to append. Python's heapq module gives the smallest heap item first, with push and pop updates in O(log k). A k-way merge is the standard name for combining many sorted inputs into one sorted output (Wikipedia: k-way merge).

The heap is small because it stores one visible head from each list, not every node.

Merge k lists: the slow way first

The direct approach is to keep k pointers, one per list, and scan all k heads to find the smallest next node:

while at least one list still has a head:
    best = the smallest current head after scanning all k lists
    append best to the answer
    advance only the list that gave best

This works, but it spends O(k) work for every output node. If the total number of nodes is N, that is O(Nk). The repeated question is: "which current head is smallest?" That is exactly the question a min-heap answers without scanning every list.

Merge k lists: the heap way

After import heapq, keep only one candidate from each list in the heap. The tuple stores (value, list_id, node); list_id breaks ties when two node values are equal, so Python never has to compare raw ListNode objects.

def mergeKLists(lists):
    heap = []                                      # current list heads
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = tail = ListNode()                      # answer builder
    while heap:
        _, i, node = heapq.heappop(heap)           # smallest head now
        tail.next = node; tail = node              # append it
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Notice the discipline: the heap never stores every node. It stores the current head of each unfinished list. Popping a node creates exactly one new candidate: that node's successor.

Every pop advances exactly one list, so only that list contributes the next heap item.

Transfer: same pattern, new costume

Imagine k sorted arrays of server timestamps. You need one sorted stream of all timestamps.

Before scrolling: predict what should live in the heap. Is it every timestamp, one timestamp per array, or only the final answer? Say the invariant out loud.

What the trade buys you

Here N is the total number of nodes across all lists, and k is the number of lists. Output space is not counted in the table.

Practice — answer before you scroll past

Your move (tonight)

Solve Merge k Sorted Lists in your Notion tracker using the cycle — predict → attempt → compare → encode.

1. Predict: name the heap contents before coding: one head per list.
2. Attempt: code the heap loop before watching any solution.
3. Compare: check whether your heap stores too much, too little, or exactly one head per unfinished list.
4. Encode: write the invariant from this page in your own words.