Merge K Sorted Arrays

 1 public class KSortedArray {
 2     public static int[] mergeKSortedArray(int[][] arr) {
 3         // PriorityQueue is heap in Java
 4         PriorityQueue<ArrayContainer> queue = new PriorityQueue<ArrayContainer>();
 5         int total = 0;
 6 
 7         // add arrays to heap
 8         for (int i = 0; i < arr.length; i++) {
 9             queue.add(new ArrayContainer(arr[i], 0));
10             total = total + arr[i].length;
11         }
12 
13         int m = 0;
14         int result[] = new int[total];
15 
16         // while heap is not empty
17         while (!queue.isEmpty()) {
18             ArrayContainer ac = queue.poll();
19             result[m++] = ac.arr[ac.index];
20 
21             if (ac.index < ac.arr.length - 1) {
22                 queue.add(new ArrayContainer(ac.arr, ac.index + 1));
23             }
24         }
25         return result;
26     }
27 
28     public static void main(String[] args) {
29         int[] arr1 = { 1, 3, 5, 7 };
30         int[] arr2 = { 2, 4, 6, 8 };
31         int[] arr3 = { 0, 9, 10, 11 };
32 
33         int[] result = mergeKSortedArray(new int[][] { arr1, arr2, arr3 });
34         System.out.println(Arrays.toString(result));
35     }
36 }
37 
38 class ArrayContainer implements Comparable<ArrayContainer> {
39     int[] arr;
40     int index;
41 
42     public ArrayContainer(int[] arr, int index) {
43         this.arr = arr;
44         this.index = index;
45     }
46 
47     @Override
48     public int compareTo(ArrayContainer o) {
49         return this.arr[this.index] - o.arr[o.index];
50     }
51 }