When dealing with multiple sorted arrays, a common challenge arises: how can we efficiently merge these arrays into a single sorted list? This problem is particularly relevant for situations where you continuously receive input in sorted order. In this post, we'll delve into a structured approach using a priority queue (also known as a min-heap) to achieve this efficiently.

Problem Statement

Assume you have k sorted arrays, and you want to merge these into a single sorted array. For instance, consider the following arrays:

• Array 1: [1, 4, 7]
• Array 2: [2, 5, 8]
• Array 3: [0, 6, 10]

Your goal is to merge these arrays into one sorted array:
Output: [0, 1, 2, 4, 5, 6, 7, 8, 10]

Approach

Using a priority queue allows us to efficiently keep track of the smallest elements across the k arrays at any point in time. Here's a step-by-step breakdown of the approach:

1. Initialize a min-heap: This will help us keep track of the smallest elements.
2. Insert the first element of each array into the heap: We need to know what the current smallest elements are.
3. Extract the minimum element from the heap: This is effectively the smallest among all the arrays.
4. Insert the next element from the same array: After extracting the minimum, we need to see if there are more elements in that particular array.
5. Repeat until the heap is empty.

Implementation in Java

Let’s implement this concept using Java:

import java.util.PriorityQueue;

public class MergeKSortedArrays {
    static class ArrayEntry {
        int value; // The value of the element
        int arrayIndex; // The index of the array from which the value is taken
        int elementIndex; // The index of the element in its array

        public ArrayEntry(int value, int arrayIndex, int elementIndex) {
            this.value = value;
            this.arrayIndex = arrayIndex;
            this.elementIndex = elementIndex;
        }
    }

    public static int[] mergeKSortedArrays(int[][] arrays) {
        // Create a priority queue (min-heap)
        PriorityQueue<ArrayEntry> minHeap = new PriorityQueue<>((a, b) -> a.value - b.value);
        
        // Initialize the min-heap with the first element of each array
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                minHeap.offer(new ArrayEntry(arrays[i][0], i, 0));
            }
        }

        int totalElements = 0; 
        for (int[] array : arrays) {
            totalElements += array.length;
        }
        
        int[] mergedArray = new int[totalElements];
        int currentIndex = 0;

        while (!minHeap.isEmpty()) {
            // Get the smallest entry
            ArrayEntry smallest = minHeap.poll();
            mergedArray[currentIndex++] = smallest.value;
            
            // If there are more elements in the same array, add the next element to the heap
            if (smallest.elementIndex + 1 < arrays[smallest.arrayIndex].length) {
                minHeap.offer(new ArrayEntry(arrays[smallest.arrayIndex][smallest.elementIndex + 1], smallest.arrayIndex, smallest.elementIndex + 1));
            }
        }

        return mergedArray;
    }

    public static void main(String[] args) {
        int[][] arrays = {
            {1, 4, 7},
            {2, 5, 8},
            {0, 6, 10}
        };

        int[] mergedResult = mergeKSortedArrays(arrays);
        for (int num : mergedResult) {
            System.out.print(num + " ");
        }
    }
}

Explanation of the Code

1. ArrayEntry class: This class is our utility that holds the value of the element, along with the index of the array it came from and its position in that array.
2. Priority Queue: We utilize a min-heap to always extract the smallest element efficiently.
3. Populating the Heap: Initially, we populate the heap with the first element from each sorted array.
4. Merging Logic: We repetitively extract the smallest element and add the next element from the respective array until all elements are processed.

Complexity Analysis

• Time Complexity: The total time complexity for this approach is O(N log k), where N is the total number of elements across all arrays, and k is the number of arrays. The log k factor arises because we perform log-k operations to maintain the heap each time we insert or remove an element.
• Space Complexity: The space complexity is O(k) since we're storing k elements in the min-heap at any time.

The efficiency of this algorithm becomes particularly beneficial when k (number of arrays) is small relative to N (number of total elements).