Merge k sorted lists

Merge three sorted lists into one sorted list.

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

import heapq
def merge_k(lists):
    h = [(l[0], i, 0) for i, l in enumerate(lists) if l]
    heapq.heapify(h); out = []
    while h:
        v, i, j = heapq.heappop(h)
        out.append(v)
        if j + 1 < len(lists[i]):
            heapq.heappush(h, (lists[i][j + 1], i, j + 1))
    return out