13. Merge K Sorted Request Queues into a Global Dispatch Order

Problem

A lab's inference gateway shards incoming requests across k worker processes for admission control; each worker maintains its own local queue of requests already sorted by priority score (lower score means it should be dispatched sooner). A dispatcher needs to merge these k sorted queues into a single globally-ordered dispatch sequence without re-sorting everything from scratch, since each queue is already sorted and can be large.

Given a list of k already-sorted queues (possibly empty, possibly different lengths), return every element from every queue in one fully sorted list.

Source: src/13_merge_k_sorted_request_queues.py

def merge_k_sorted_queues(queues: list[list[int]]) -> list[int]:

>>> merge_k_sorted_queues([[1, 4, 7], [2, 5, 8], [3, 6, 9]])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> merge_k_sorted_queues([[1, 2, 3], [], [0]])
[0, 1, 2, 3]

Step-by-Step Approach

1. Notice that at any point during the merge, the smallest not-yet-output element must be the head of one of the k queues — so you never need to look further than one element into each queue at a time.
2. Seed a min-heap with the head element of every non-empty queue, storing (value, queue_index, element_index) so you know which queue and position each head came from.
3. Repeatedly pop the smallest entry from the heap and append its value to the result — that's guaranteed to be the next-smallest element overall.
4. After popping a value from queue q at position i, push queue q's next element (position i + 1) onto the heap, if one exists — this "advances" that queue by one.
5. Stop when the heap is empty; every queue has been fully drained and the result list is the complete sorted merge.
6. Including queue_index (and element_index) as heap tie-breakers avoids Python trying to compare two queues' raw values with equal priority as a fallback, which would error if the queue elements themselves weren't comparable (not relevant for plain ints here, but good habit for arbitrary payloads).

The key insight is that a heap turns "which of k sorted streams has the next-smallest element" into an O(log k) question instead of an O(k) linear scan across all queue heads on every step, which is what separates a proper k-way merge from just concatenating and sorting everything (O(n log n) instead of O(n log k)).

Reference solution

import heapq


def merge_k_sorted_queues(queues: list[list[int]]) -> list[int]:
    # min-heap holds at most one "head" element per queue at a time:
    # O(n log k) time (n = total elements, k = number of queues), O(k) heap space
    heap = []
    for queue_index, queue in enumerate(queues):
        if queue:
            heapq.heappush(heap, (queue[0], queue_index, 0))
    result = []
    while heap:
        value, queue_index, elem_index = heapq.heappop(heap)
        result.append(value)
        next_index = elem_index + 1
        if next_index < len(queues[queue_index]):
            heapq.heappush(heap, (queues[queue_index][next_index], queue_index, next_index))
    return result

Key Functions & Tricks

• heapq.heappush / heapq.heappop — maintain the "current smallest head across all queues" in O(log k) per operation.
• (value, queue_index, element_index) tuple — carries enough context to advance the correct queue after popping, and doubles as a heap tie-breaker.
• seeding one head per queue — the core invariant that keeps the heap bounded to size k instead of n.
• enumerate(queues) — pairs each queue with its index for the initial seed pass.
• skipping empty queues — avoids pushing an out-of-range head for a queue that starts empty.

How to Recognize This Pattern