C++でストリーム内の最大K個の数値の平均を求めるアルゴリズム

ストリーム内の最大K個の数値の平均とは

ストリーム内の数値の平均とは、数値を挿入するたびにその時点での平均を計算することを意味します。しかし本記事で扱う問題では、ストリーム内の最大K個の数値の平均を求める必要があります。つまり、平均の計算対象となるのは配列のうち上位K個の数値のみです。新しい数値を追加する際、その数値が現在平均に寄与している数値のいずれよりも大きい場合にのみ計算に反映され、そうでなければ平均は変化しません。

概念をより深く理解するために、具体例を見てみましょう。

入力 : n = 4 , k = 3 , array = { 4, 9, 1 , 5} , stream = {2, 6, 3 , 7 }
出力 : 6 , 6.66 , 6.66 , 7.33

1回目の挿入： 平均は (4 + 9 + 5) / 3 = 6 となります。2を挿入しても、平均に寄与する数値より小さいため変化はありません。

2回目の挿入： 平均は (6 + 9 + 5) / 3 = 6.66 となります。6が追加され、平均の計算対象だった4よりも大きいため、4が6に置き換えられ、平均は6.66に更新されます。

3回目の挿入： 平均は (6 + 9 + 5) / 3 = 6.66 のままです。3を挿入しても変化はありません。

4回目の挿入： 平均は (6 + 9 + 7) / 3 = 7.33 となります。7が挿入され、5を置き換えるため平均は7.33に更新されます。

このように、ストリーム内の最大K個の数値の平均を求める問題の概要が理解できたところで、解法を導き出しましょう。このような要素の挿入や削除が繰り返し行われる種類の問題では、ヒープ（Heap）を活用すると効率的に解を求めることができます。

アルゴリズム

ステップ1 : 配列の上位K個の要素で最小ヒープを作成する（K個の要素のうち最小値がルートに位置する）。
ステップ2 : ストリームの各要素に対して以下を実行する。
ステップ3 : その要素をヒープのルートと比較する。
ステップ4 : ルートの値がその要素より小さい場合、ルートを新しい要素に置き換える。

実装例

以下は、上記のアルゴリズムをJavaで実装したコード例です。優先度付きキュー（PriorityQueue）を最小ヒープとして利用しています。

import java.util.*;
public class Kmaxsum {
   static void max_average_k_numbers(int n, int k, int m, int[] arr, int[] query){
      double max_avg = 0.0;
      PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
      Arrays.sort(arr);
      double sum = 0;
      for (int i = n - 1; i >= n - k; i--) {
         pq.add(arr[i]);
         sum = sum + arr[i];
      }
      for (int i = 0; i < m; i++) {
         if (query[i] > pq.peek()) {
            int polled = pq.poll();
            pq.add(query[i]);
            sum = sum - polled;
            sum = sum + query[i];
         }
         max_avg = sum / (double)k;
         System.out.println(max_avg);
      }
   }
   public static void main(String[] args){
      int n = 4;
      int k = 3;
      int m = 4;
      int[] arr = new int[] { 4, 9, 1 , 5 };
      int[] query = new int[] { 2, 6, 3 , 7 };
      System.out.println("The sum of K max sums of stream is : ");
      max_average_k_numbers(n, k, m, arr, query);
   }
}

実行結果

The sum of K max sums of stream is :
6.0
6.666666666666667
6.666666666666667
7.333333333333333

この実装では、まず配列をソートして上位K個の要素を最小ヒープに格納し、合計値を計算します。その後、ストリームから各要素を受け取るたびにヒープのルート（現在上位K個の中で最小の値）と比較し、新しい要素の方が大きければ置き換えます。合計値の更新と平均の計算は毎回O(1)で行え、ヒープ操作はO(log K)で済むため、全体として非常に効率的なアルゴリズムとなっています。