C++でk個のソート済み配列からm番目に小さい値を効率的に求める方法

この問題では、サイズの異なるk個の配列が与えられます。目的は、k個のソート済み配列全体の中からm番目に小さい値を見つけることです。

問題の概要

すべての配列を1つにマージしたと仮定したとき、その中でm番目に小さい要素を求めます。

入出力例

入力: m = 4
arr[][] = { {4, 7},
{2, 5, 6},
{3, 9, 12, 15, 19} }

出力: 5

解説:

すべての配列をマージしてソートすると「2, 3, 4, 5, 6, 7, 9, 12, 15, 19」となり、4番目の要素は5であることがわかります。

解法アプローチ

シンプルな解法：マージしてソートする

最も単純な方法は、すべての配列を1つの配列にマージし、昇順にソートすることです。ソート後の配列では、インデックス(m-1)の位置にある要素がm番目に小さい値となります。この値を返すだけで完成です。ただし、この方法の時間計算量はO(N log N)(Nは全要素数)となるため、データ量が多い場合には非効率になる点に注意が必要です。

効率的な解法：最小ヒープ(min heap)を活用する

より効率的なのが最小ヒープ(ミンヒープ)というデータ構造を使ったアプローチです。手順は以下の通りです。

1. 各配列の先頭要素を最小ヒープに挿入します。
2. ヒープから最小要素を取り出す操作をm回繰り返します。
3. 要素を取り出すたびに、その要素が属していた配列の次の要素をヒープに挿入します。
4. m回目に取り出した要素が、求めるm番目に小さい値となります。

この方法の時間計算量はO(m log k)であり、mが全要素数より十分小さい場合には大幅な高速化が期待できます。

実装例(C++)

以下は、上記の最小ヒープを使った解法をC++で実装したサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, pair<int, int> > ppi;

int findMSmallestElement(vector<vector<int> > sortedArr, int m) {
    
    priority_queue<ppi, vector<ppi>, greater<ppi> > priorQueue;

    for (int i = 0; i < sortedArr.size(); i++)
       priorQueue.push({ sortedArr[i][0], { i, 0 } });
    int count = 0;
    int i = 0, j = 0;
    while (count < m && priorQueue.empty() == false) {
       ppi curr = priorQueue.top();
       priorQueue.pop();
       i = curr.second.first;
       j = curr.second.second;
       if (j + 1 < sortedArr[i].size())
          priorQueue.push( { sortedArr[i][j + 1], { i, (j + 1) } });
       count++;
    }
    return sortedArr[i][j];
}

int main() {
    
    vector<vector<int> > arr{ {4 , 7},
                          {2, 5, 6},
                          {3, 9, 12, 15, 19}};
    int m = 6;
    cout<<m<<"th smallest value in k sorted arrays is "<<findMSmallestElement(arr, m);

    return 0;
}

実行結果

6th smallest value in k sorted arrays is 7

このプログラムでは、m = 6 を指定しているため、6番目に小さい値である「7」が出力されます。ヒープには常に各配列の候補要素だけが保持されるため、メモリ効率にも優れています。