Merge several sorted lists

Merging two sorted lists uses two positions. For many lists, a heap keeps track of which list currently has the smallest front item. Push one entry per list: (first value, list number, 0). Repeatedly pop the smallest, add its value to the result, and if that list has a next item, push (next value, list number, position + 1). Stop when the heap is empty.

Write merge_all(lists) that returns one sorted list containing every item from every list. Lists may be empty. Do not use sort or sorted.

merge_all([[1, 4, 9], [2, 3], [], [5]])  ->  [1, 2, 3, 4, 5, 9]

import heapq

def merge_all(lists):
    ...