Introduction

If you have n sorted arrays or queues and want the minimum possible sum of exactly k chosen numbers, the core task is to repeatedly take the smallest currently available value. When each input is already sorted in ascending order, a min-heap lets you do that efficiently without merging every element into one big list first.

This is a classic heap problem because you only ever need to compare the front candidates from each source.

Problem Setup

Assume each array or queue is sorted from smallest to largest. You may pick values from any source, and you want the smallest possible total after choosing exactly k values.

For example, if the inputs are:

• '[1, 4, 9]'
• '[2, 3, 10]'
• '[5, 6]'

and k = 4, then the best choice is 1 + 2 + 3 + 4 = 10.

The reason sorting matters is that once you remove the current smallest value from one source, the next candidate from that source becomes the only new value worth considering immediately.

Heap-Based Strategy

The algorithm is:

1. push the first element of every non-empty array into a min-heap
2. pop the smallest element from the heap
3. add it to the running sum
4. push the next element from the same array, if one exists
5. repeat until k elements have been taken

This works because the heap always contains the smallest not-yet-used candidate from each source.

Python Example

Here is a runnable implementation:

1import heapq
2
3
4def min_sum_k_from_sorted_arrays(arrays, k):
5    heap = []
6    total = 0
7    taken = 0
8
9    for array_index, arr in enumerate(arrays):
10        if arr:
11            heapq.heappush(heap, (arr[0], array_index, 0))
12
13    while heap and taken < k:
14        value, array_index, element_index = heapq.heappop(heap)
15        total += value
16        taken += 1
17
18        next_index = element_index + 1
19        if next_index < len(arrays[array_index]):
20            next_value = arrays[array_index][next_index]
21            heapq.heappush(heap, (next_value, array_index, next_index))
22
23    if taken < k:
24        raise ValueError("Not enough total elements to pick k numbers")
25
26    return total
27
28
29arrays = [[1, 4, 9], [2, 3, 10], [5, 6]]
30print(min_sum_k_from_sorted_arrays(arrays, 4))

The heap stores three pieces of information: the value, which array it came from, and the index inside that array.

Why This Is Better Than Full Merge

A brute-force approach would concatenate all arrays, sort the combined list, and sum the first k elements. That works, but it does more work than necessary when the inputs are already sorted.

The heap approach avoids touching every element eagerly. If the total number of arrays is n and you only need k values, the time complexity is O(k log n) after the initial heap setup. That is often much better than merging and sorting everything.

What If The Inputs Are Not Sorted

If the arrays or queues are not sorted, the heap approach no longer works directly because the front element is not guaranteed to be the smallest remaining choice from that source.

In that case you must either sort each source first or use a different selection strategy. The heap solution depends on the sorted-input guarantee.

Common Pitfalls

The biggest mistake is applying this algorithm to unsorted arrays. If the front elements are not the smallest remaining elements in their sources, the greedy heap choice is no longer valid.

Another pitfall is forgetting to handle the case where k is larger than the total number of available elements. The algorithm should either raise an error or define a clear fallback behavior.

A third issue is using a max-heap or storing the wrong tuple order in the heap. The smallest value must be the first comparison key so the heap pops the correct element.

Summary

• When each input source is sorted, a min-heap is the right tool for selecting the global next-smallest value.
• Push the first element of each array, then keep advancing only the source that supplied the last minimum.
• This yields the minimum possible sum of k selected values.
• The heap solution runs in O(k log n) time after initialization.
• The sorted-input assumption is essential for correctness.