K-Way Merge (Heap)

mediumpy_datastructures

Implement merge(lists).

Merge k lists — each already sorted in non-decreasing order — into one sorted list, using a heap (heapq) for an O(N log k) merge. Don't concatenate and sorted, and don't slice. Leave the inputs unchanged. For example merge([[1, 4, 7], [2, 3, 8], [0, 5, 9]]) == [0, 1, 2, 3, 4, 5, 7, 8, 9].

Constraints

no sorted

Your solution

Edit merge and run the real pytest suite in your browser — no install required. Your code is saved locally.

Loading the Python runtime (first run only)…

Hints

Hint 1

Push the first element of each non-empty list onto a heap as (value, list_index, elem_index).

Hint 2

Pop the smallest, emit it, and push the next element from that same list. Repeat until the heap is empty.

Stuck? Try these first

easyMerge Two Sorted Lists