C++でサイズの異なるk個のソート済み配列を効率的にマージする方法

この記事では、サイズがそれぞれ異なるk個のソート済み配列を1つの配列にマージし、ソートされた結果を出力する方法を解説します。

例えば、k = 3 で配列が {2, 4}、{3, 5, 7}、{1, 10, 11, 12} の場合、出力は次のようになります。

1 2 3 4 5 7 10 11 12

アルゴリズムの考え方：優先度付きキュー（最小ヒープ）を使う

すべての要素を単純に連結してからソートすることもできますが、その場合の計算量は O(N log N)（Nは全要素数）になります。一方、各配列がすでにソートされているという性質を活かせば、優先度付きキュー（min-heap）を使って O(N log k) で効率的にマージできます。ここで k は配列の個数です。

基本的なアイデアは「各配列の先頭要素だけをヒープに入れ、最小値を取り出したら、その要素が属していた配列の次の要素をヒープに追加する」というものです。これにより、常に全体で最小の候補だけを比較対象にできます。

手順

• 最初の要素が整数、2番目の要素が整数ペア（配列インデックスと要素位置）であるペア型を定義し、ppi と名付けます。
• 結果を格納する配列 op を定義します。
• 優先度付きキュー q を定義します（C++では greater を指定して最小ヒープとして動作させます）。
• i = 0 から arr のサイズ未満まで繰り返します。
  • 各配列の先頭要素 (arr[i][0], {i, 0}) をキューに挿入します。
• キューが空になるまで以下を繰り返します。
  • キューの先頭要素を current_element として取得し、削除します。
  • i に配列のインデックス、j にその配列内の位置を取り出します。
  • current_element の値（first要素）を op の末尾に追加します。
  • j + 1 < arr[i].size() が成り立つ場合、つまり同じ配列にまだ要素が残っている場合は、次の要素 (arr[i][j+1], {i, j+1}) をキューに挿入します。
• op を返します。

C++での実装例

以下のコードで実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
#define ppi pair<int,pair<int,int>>

vector<int> merge(vector<vector<int>> arr) {
    vector<int> op;
    // greater を指定して最小ヒープとして動作させる
    priority_queue<ppi, vector<ppi>, greater<ppi>> queue;
    // 各配列の先頭要素をヒープに登録
    for (int i = 0; i < arr.size(); i++)
        queue.push({ arr[i][0], { i, 0 } });
    while (queue.empty() == false) {
        ppi current_element = queue.top();
        queue.pop();
        int i = current_element.second.first;   // 配列のインデックス
        int j = current_element.second.second;  // 配列内の位置
        op.push_back(current_element.first);
        // 同じ配列に次の要素があればヒープへ追加
        if (j + 1 < arr[i].size())
            queue.push({ arr[i][j + 1], { i, j + 1 } });
    }
    return op;
}

int main() {
    vector<vector<int>> arr{ { 2, 4 }, { 3, 5, 7 }, { 1, 10, 11, 12 } };
    vector<int> output = merge(arr);
    for (int i = 0; i < output.size(); i++)
        cout << output[i] << " ";
    return 0;
}

入力

{{ 2,4}, { 3,5,7 }, { 1, 10, 11, 12 }}

出力

1 2 3 4 5 7 10 11 12

計算量について

全要素数を N、配列の個数を k とすると、各要素は最大でも log k 回のヒープ操作に関わるため、時間計算量は O(N log k) となります。これは全要素を連結後にソートする O(N log N) よりも、配列数 k が小さい場合に有利です。また、使用するメモリはヒープに常時保持される最大 k 個の要素分なので、空間計算量は O(k) です。

まとめ

サイズの異なる複数のソート済み配列をマージする際は、優先度付きキュー（最小ヒープ）を活用することで、元のソート済みという性質を最大限に活かした高速な処理が可能になります。C++では std::priority_queue に std::greater を渡すだけで簡単に最小ヒープを実現できるため、実装もシンプルです。外部ソートやストリームデータのマージなど、応用範囲も広いテクニックなので、ぜひ覚えておきましょう。