Merge multiple sorted arrays using min-heap

Problem

You are given k sorted arrays of integers:

• arrays[0], arrays[1], ..., arrays[k-1]
• Each arrays[i] is sorted in non-decreasing order.
• The total number of elements across all arrays is N.

Your task is to merge these k sorted arrays into a single sorted array (or list) containing all N elements.

You should design an algorithm that is asymptotically optimal in terms of time complexity for large k and N. A straightforward approach that repeatedly scans all array heads at each step is too slow when k is large.

Output: a single sorted sequence of all elements from the k arrays.

Example

Input:

• k = 3
• arrays[0] = [1, 4, 9]
• arrays[1] = [2, 6]
• arrays[2] = [0, 3, 7, 8]

Output:

• [0, 1, 2, 3, 4, 6, 7, 8, 9]

Constraints

• 1 <= k <= 10^5
• Each array length can be zero or more.
• Total number of elements N across all arrays: 0 <= N <= 10^6 (assume this upper bound for complexity discussion).
• Integer values fit in 32-bit signed range.

Requirements

1. Describe an efficient algorithm for this problem, including:

• Data structures you would use.
• Time and space complexity.

1. Then implement the function that merges the arrays following your algorithm.

(Hint: Consider a priority-based data structure that efficiently gives you the smallest current element among the k arrays.)