Merge k sorted lists with a priority_queue — interview question

Each of k exam halls sends a list of marks already sorted in ascending order. Merge all the lists into one sorted list.

Use a min-heap (std::priority_queue with std::greater) that holds only one candidate per list at a time, instead of concatenating everything and sorting.

Constraints

1 ≤ k ≤ 1000
0 ≤ m, and the total number of values N is at most 10^5
−10^9 ≤ each value ≤ 10^9

Input and output

Input: First line: k. Then k lines. Each line starts with m (the length of that list), followed by m integers in non-decreasing order.
Output: One line with all values in non-decreasing order, separated by spaces (an empty line if every list is empty).

Examples

Input 1

Output

0 1 2 3 4 5 5 9 10

The heap starts with 1, 2 and 0, and always outputs the smallest.

Input 2

2
0
3 -2 -2 7

Output

-2 -2 7

An empty list contributes nothing.

Show hints

priority_queue is a max-heap by default. Pass greater<> as the third template argument for a min-heap.
Store (value, list index, position in list), so after popping you know which element to push next.

Show the explanation

Keep a min-heap of (value, list, index) that starts with the first element of every non-empty list.

Repeat until the heap is empty:

Pop the smallest entry and print its value.
If that list has another element, push (lists[l][i+1], l, i+1).

The heap never holds more than k entries, so each push or pop costs O(log k), and the total is O(N log k) for N values. Concatenating and sorting costs O(N log N). The heap approach also works when the lists are streams that do not fit in memory, which is how external merge sort works.

C++ details:

priority_queue<T, vector<T>, greater<T>> gives a min-heap. Tuples compare element by element, so ties on value are broken by list index. That makes the merge stable and deterministic.
top() returns a reference to the smallest element and pop() removes it. Copy the top element before calling pop().

Python has the same tool: heapq.merge(*lists) returns a lazy iterator that does this merge.

Original UniCircle question. Last reviewed 22 Oct 2026.