【C++】要素を挿入するたびにK番目に小さい要素を求める方法

はじめに

このチュートリアルでは、要素を挿入するたびにK番目に小さい要素を求めるアルゴリズムを解説します。

この問題は、最小ヒープ(min-heap)を利用することで効率よく解決できます。それでは、プログラムを完成させるための手順を順番に見ていきましょう。

アルゴリズムの手順

• ランダムなデータで配列を初期化します。
• 優先度付きキュー(priority queue)を初期化します。
• 最初の k - 1 個の段階では、まだ K 番目に小さい要素が存在しないため、「- 」のような任意の記号を出力しておきます。
• k 番目から n 番目まで繰り返すループを作成します。
  • 最小ヒープのルート(先頭要素)を出力します。
  • 新しい要素がヒープのルートより大きい場合は、ルートを取り出し(pop)、代わりにその要素を挿入(push)します。

C++ では、priority_queue の第3テンプレート引数に greater<int> を指定することで、最も小さい値が常に先頭に来る最小ヒープとして扱えるようになります。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void findKthSmallestElement(int elements[], int n, int k) {
   priority_queue<int, vector<int>, greater<int>> queue;
   for (int i= 0; i < k - 1; i++) {
      queue.push(elements[i]);
      cout << "- ";
   }
   queue.push(elements[k-1]);
   for (int i = k; i < n; i++) {
      cout << queue.top() << " ";
      if (elements[i] > queue.top()) {
         queue.pop();
         queue.push(elements[i]);
      }
   }
   cout << queue.top() << endl;
}
int main() {
   int arr[] = {3, 5, 6, 2, 7, 8, 2, 3, 5, 9};
   findKthSmallestElement(arr, 10, 5);
   return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

- - - - 2 3 3 3 5 5

計算量

このアルゴリズムでは、各要素ごとにヒープへの挿入・削除を行います。ヒープのサイズは最大でも k であるため、全体の時間計算量は O(n log k)、必要なメモリ領域は O(k) となります。全要素を毎回ソートし直す方法(O(n² log n))と比べて非常に効率的です。

まとめ

今回は、最小ヒープ(優先度付きキュー)を使って、挿入のたびに K 番目に小さい要素を求める方法を紹介しました。このチュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。