C++で整数配列の中央値を求めるプログラム【2つのヒープによる効率的な実装】

ここでは、MedianClass というクラスを実装することを考えます。このクラスには、次の2つのメソッドを持たせます。

• add(value)：データ構造に新しい値を追加します。

• median()：現在データ構造に格納されているすべての数値の中央値を求めます。

例えば、5、3、8 の順に値を追加した後で中央値を取得すると、出力は 5.0 になります。その後、さらに 9 を追加して中央値を取得すると、出力は 6.5 になります。

解き方のアプローチ

この問題は、2つの優先度付きキュー（ヒープ）を組み合わせることで効率的に解けます。片方のヒープには小さい方半分の値を、もう片方には大きい方半分の値を保持し、常に両者のバランスを保つことで、中央値を O(1) で取り出せるようにします。

具体的には、以下の手順に従います。

• 優先度付きキュー left（最大ヒープ）と right（最小ヒープ）を定義します。

• addNum メソッドを定義します。数値を入力として受け取り、次のように処理します。

• left が空であるか、num が left の先頭要素より小さい場合は、

  • num を left に挿入します。

• それ以外の場合は、

  • num を right に挿入します。

• left のサイズが right のサイズより小さい場合は、

  • temp := right の先頭要素

  • right から要素を削除する

  • temp を left に挿入する

• left のサイズ − right のサイズ > 1 となる場合は、

  • temp := left の先頭要素

  • left から要素を削除する

  • temp を right に挿入する

• findMedian メソッドを定義します。このメソッドは次のように動作します。

left のサイズが right のサイズより大きい場合は left の先頭要素をそのまま返し、それ以外の場合は (left の先頭要素 + right の先頭要素) ÷ 2 を返します。

それでは、理解を深めるために以下の実装例を見てみましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
typedef double lli;
class MedianClass {
   priority_queue <int> left;
   priority_queue <int, vector <int>, greater<int>> right;
   public:
   void addNum(int num) {
      if(left.empty() || num<left.top()){
         left.push(num);
      }else right.push(num);
      if(left.size()<right.size()){
         lli temp = right.top();
         right.pop();
         left.push(temp);
      }
      if(left.size()-right.size()>1){
         lli temp = left.top();
         left.pop();
         right.push(temp);
      }
   }
   double findMedian() {
      return
      left.size()>right.size()?left.top():(left.top()+right.top())*0.5;
   }
};
main(){
   MedianClass ob;
   ob.addNum(5);
   ob.addNum(3);
   ob.addNum(8);
   cout << ob.findMedian() << " ";
   ob.addNum(9);
   cout << ob.findMedian() << endl;
}

入力

ob.addNum(5);
ob.addNum(3);
ob.addNum(8);
cout << ob.findMedian() << endl;
ob.addNum(9);
cout << ob.findMedian() << endl;

出力

5.0
6.5

計算量について

この実装では、値の追加（addNum）はヒープへの挿入となるため O(log n)、中央値の取得（findMedian）はヒープの先頭要素を参照するだけなので O(1) で行えます。ストリーム形式で次々と数値が与えられ、その都度中央値を求めたいような場面で非常に有効な手法です。