[解決済み】整数の流れから実行中央値を求める

質問

重複している可能性があります。

C言語によるローリングメディアンアルゴリズム

データストリームから整数が読み込まれるとする。これまでに読み込まれた要素の中央値を効率的に求めよ。

私が読んだ解決策。左側の最大ヒープで実効中央値より小さい要素を、右側の最小ヒープで実効中央値より大きい要素を表現すればよい。

受信した要素を処理した後、ヒープ内の要素数は最大で1要素分異なる。両ヒープの要素数が同じ場合は、ヒープのルートデータの平均を実効中央値とする。ヒープがバランスしていない場合、より多くの要素を含むヒープのルートから有効な中央値を選択する。

しかし、最大ヒープと最小ヒープをどのように構築するのか、つまり、ここで有効な中央値をどのように知ることができるのでしょうか？最大ヒープに1要素入れて、次の1要素を最小ヒープに入れるというように、すべての要素に入れることになると思うのですが。もし私が間違っていたら、訂正してください。

どのように解決するのですか？

ストリームデータから実行中央値を求めるには、さまざまなソリューションがありますが、それらについて、回答の一番最後に簡単に説明します。

質問は、特定のソリューション（最大ヒープ/最小ヒープソリューション）の詳細についてであり、ヒープベースのソリューションがどのように機能するかは、以下のように説明されています。

最初の2つの要素について、小さい方を左のmaxHeapに、大きい方を右のminHeapに追加します。そして、ストリームデータを1つずつ処理します。

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

そうすると、任意のタイミングで、このように中央値を計算することができます。

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

さて、解答の冒頭でお約束した問題全般についてお話します。データの流れから実行中央値を求めるのは大変な問題で、そのために 厳密解 というのは、一般的なケースでは、メモリ制約があるため、おそらく不可能です。一方、データに利用できる特性があれば、効率的な特化解を開発することができる。例えば、データが積分型であることが分かっている場合、そのデータに対して カウントソート これは、定数メモリ定数時間のアルゴリズムを与えることができます。ヒープベースの解決策は、他のデータ型（double）にも使えるので、より一般的な解決策と言えます。最後に、正確な中央値を必要とせず、近似値で十分な場合は、データの確率密度関数を推定し、それを使って中央値を推定することができます。