Javaでk個のソート済み配列をマージする方法|優先度付きキューを使った効率的な実装

本記事では、「n」個の配列が与えられる状況を想定します。ここでは例として、整数型の3つの配列 arr1[]、arr2[]、arr3[] を扱います。課題は、与えられたすべての整数配列を、実行時に結果の配列がソート済みの状態になるようにマージすることです。

具体例で理解しよう

例1

入力:

int a[] = {21, 22, 23, 24};
int b[] = {28, 31, 35};

出力:

int resultant[] = {21, 22, 23, 24, 28, 31, 35};

解説: 各配列の要素は結果配列に追加される前に互いに比較され、それぞれ適切な位置へと挿入されます。

例2

入力:

int a[] = {1, 3, 5, 7, 9, 11, 13};
int b[] = {14, 16, 18};
int c[] = {19, 20, 21, 22};

出力:

int resultant[] = {1, 3, 5, 7, 9, 11, 13, 14, 16, 18, 19, 20, 21, 22};

解説: 例1と同様に、要素は追加前に比較され、結果配列内の正しい位置に配置されます。

プログラムで使用するアプローチ

この問題は優先度付きキュー(PriorityQueue)、すなわちミンヒープを利用することで効率的に解決できます。手順は以下の通りです。

• 3つの整数配列 arr1[]、arr2[]、arr3[] と結果配列 result[] を用意し、mergeSortedArray(new int[][] { arr1, arr2, arr3 }) を呼び出します。
• メソッド mergeSortedArray() 内部の処理は次の通りです。
  • PriorityQueue 型の変数 queue と、全要素数を表す変数 total を宣言し、total を 0 で初期化します。
  • for ループで i を 0 から配列の個数まで回し、各配列を ArrayBucket オブジェクトとしてキューに追加するとともに、total に各配列の長さを加算します。
  • m を 0 に初期化し、結果格納用の整数配列 result[] を total のサイズで生成します。
  • キューが空でない間(queue.isEmpty() == false)、queue.poll() で最小値を持つバケットを取り出し、result[m++] に ac.arr[ac.index] を代入します。さらに、ac.index が ac.arr.length - 1 より小さい場合は、次のインデックスを指す新しい ArrayBucket をキューに追加します。
  • 最終的に result を返します。

Javaコード例

import java.util.Arrays;
import java.util.PriorityQueue;

class ArrayBucket implements Comparable<ArrayBucket> {
    int[] arr;
    int index;

    public ArrayBucket(int[] arr, int index) {
        this.arr = arr;
        this.index = index;
    }

    @Override
    public int compareTo(ArrayBucket o) {
        return this.arr[this.index] - o.arr[o.index];
    }
}

public class testClass {
    public static int[] mergeSortedArray(int[][] arr) {
        PriorityQueue<ArrayBucket> queue = new PriorityQueue<ArrayBucket>();
        int total = 0;
        for (int i = 0; i < arr.length; i++) {
            queue.add(new ArrayBucket(arr[i], 0));
            total = total + arr[i].length;
        }
        int m = 0;
        int result[] = new int[total];
        while (!queue.isEmpty()) {
            ArrayBucket ac = queue.poll();
            result[m++] = ac.arr[ac.index];
            if (ac.index < ac.arr.length - 1) {
                queue.add(new ArrayBucket(ac.arr, ac.index + 1));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = { 1, 3, 5, 7 };
        int[] arr2 = { 2, 4, 6, 8 };
        int[] arr3 = { 0, 9, 10, 11 };
        int[] result = mergeSortedArray(new int[][] { arr1, arr2, arr3 });
        System.out.println("The final merged sorted array is :- " + Arrays.toString(result));
    }
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

The final merged sorted array is :- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

計算量の目安

このアプローチの時間計算量は O(N log k) です(N は全要素数の合計、k は配列の個数)。各要素ごとにヒープへの挿入・削除が O(log k) で行われるため、全要素を連結してからソートする O(N log N) の方法よりも、配列数 k が小さい場合に効率的に動作します。