Exercise 2 solution

    import heapq

    def heap_sort(items):
        h = list(items)             # copy so the input is untouched
        heapq.heapify(h)
        return [heapq.heappop(h) for _ in range(len(h))]

    def merge_sorted(*lists):
        h = []
        for i, lst in enumerate(lists):
            if lst:
                h.append((lst[0], i, 0))     # (value, which list, position)
        heapq.heapify(h)
        out = []
        while h:
            value, i, pos = heapq.heappop(h)
            out.append(value)
            if pos + 1 < len(lists[i]):
                heapq.heappush(h, (lists[i][pos + 1], i, pos + 1))
        return out

    data = [7, 2, 9, 4, 4, 1]
    print(heap_sort(data), data)
    a, b, c = [1, 4, 9], [2, 3, 10], [0, 5]
    print(merge_sorted(a, b, c))
    print(merge_sorted([], [3, 6]), merge_sorted())
    print(merge_sorted(a, b, c) == list(heapq.merge(a, b, c)))

Output:
    [1, 2, 4, 4, 7, 9] [7, 2, 9, 4, 4, 1]
    [0, 1, 2, 3, 4, 5, 9, 10]
    [3, 6] []
    True

heap_sort is heapify (linear) plus n pops (each logarithmic), so O(n log n)
overall. The merge keeps only one candidate per input list in the heap, so
it holds at most as many items as there are lists and each output value
costs one pop and at most one push. The list index stored in the tuple
tells us which list to take the next value from, and it breaks ties between
equal values. This is what heapq.merge does for you, lazily.